统计方案2

题目描述:

小B写了一个程序，随机生成了n个正整数，分别是a[1]..a[n]，他取出了其中一些数，并把它们乘起来之后模p，得到了余数c。但是没过多久，小B就忘记他选了哪些数，他想把所有可能的取数方案都找出来。你能帮他计算一下一共有多少种取数方案吗？请把最后的方案数模1000000007后输出。

小B记得他至少取了一个数。

输入格式:

第一行三个正整数n,p,c，含义如题目所述。

接下来一行有n个正整数，表示生成的n个随机数。

输出格式:

一个数，方案数模1000000007。

样例输入:

2 7 2
1 2

样例输出:

2

提示:

注意，c不一定小于p

对于30%的数据，n≤16

另有30%的数据，p≤10000

对于100%的数据，n≤32, p≤10^9, c≤10^9, a[i]<p, p是质数

时间限制: 1000ms
空间限制: 256MB

---