[SDOI2015]序列统计
题号：NC20373
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。 
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：
给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。
小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。
另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

输入描述:

一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。
第二行，|S|个整数，表示集合S中的所有元素。

输出描述:

一行，一个整数，表示你求出的种类数mod 1004535809的值。
示例1

输入

复制 
4 3 1 2
1 2

输出

复制 
8

备注:

对于10%的数据，；
对于30%的数据，；
对于60%的数据，；
对于100%的数据，。
m为质数，输入数据保证集合S中元素不重复。