luogu#P3321. [SDOI2015] 序列统计

    ID: 7351 远端评测题 1000ms 125MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>2015山东素数判断质数筛法概率论统计快速傅里叶变换,FFT

[SDOI2015] 序列统计

题目描述

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

小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:给定整数 xx,求所有可以生成出的,且满足数列中所有数的乘积 mod m\bmod \ m 的值等于 xx 的不同的数列的有多少个。

小C认为,两个数列 AABB 不同,当且仅当 i s.t. AiBi\exists i \text{ s.t. } A_i \neq B_i。另外,小C认为这个问题的答案可能很大,因此他只需要你帮助他求出答案对 10045358091004535809 取模的值就可以了。

输入格式

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

输出格式

一行一个整数表示答案。

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%10\% 的数据,1n10001\le n \le 1000
对于 30%30\% 的数据,3m1003 \le m \le 100
对于 60%60\% 的数据,3m8003 \le m \le 800
对于 100%100\% 的数据,1n1091 \le n \le 10^93m80003 \le m \le 80001x<m1\le x < m
mm 为质数,输入数据保证集合 SS 中元素不重复。