P4000 - sequence

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：0 通过：0

给定一个集合S，里面元素都是小于M的非负整数。
现在要生成一个长度为N的数列，每个数都选自集合S。
现在给出一个x，要求生成的数列里的元素乘积mod M后等于x。
问有多少中生成数列。
其中1,1,2,2与1,2,1,2是两种数列。

第一行4给整数N,M,x,|S|，其中|S|为S集合的大小
第二行|S|给整数，表示S集合中的元素
1<=N<=10^9
3<=M<=8000，且为质数
1<=x<=M-1
保证S集合中的数不重复

输出一个整数，表示生成数列的数目，答案mod 1004535809

4 3 1 2
1 2

4000: sequence