#2183. 「SDOI2015」序列统计

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 C 有一个集合 S ,里面的元素都是小于 M 的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为 N 的数列,数列中的每个数都属于集合 S

小 C 用这个生成器生成了许多这样的数列。但是小 C 有一个问题需要你的帮助:给定整数 x ,求所有可以生成出的,且满足数列中所有数的乘积 \bmod M 的值等于 x 的不同的数列的有多少个。小 C 认为,两个数列 \{A_i\} \{B_i\} 不同,当且仅当至少存在一个整数 i ,满足 A_i \neq B_i 。另外,小 C 认为这个问题的答案可能很大,因此他只需要你帮助他求出答案 \mod 1004535809 的值就可以了。

输入格式

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

输出格式

一行,一个整数,表示你求出的种类数 \mod 1004535809 的值。

样例

样例输入

4 3 1 2
1 2

样例输出

8

样例解释

可以生成的满足要求的不同的数列有 (1,1,1,1) (1,1,2,2) (1,2,1,2) (1,2,2,1) (2,1,1,2) (2,1,2,1) (2,2,1,1) (2,2,2,2)

数据范围与提示

对于 10\% 的数据, 1 \leq N \leq 1000
对于 30\% 的数据, 3 \leq M \leq 100
对于 60\% 的数据, 3 \leq M \leq 800
对于全部的数据, 1 \leq N \leq 10^9,\ 3 \leq M \leq 8000 M 为质数, 1 \leq x \leq M-1 ,输入数据保证集合 S 中元素不重复。