题目描述

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

你能帮他计算一下一共有多少种取数方案吗？请把最后的方案数模1000000007后输出。

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

输入格式

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

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

输出格式

一行一个数，方案数模1000000007。

2 7 2
1 2

2

数据规模与约定

对于30%的数据，n≤16。

另有30%的数据，p≤10000。

对于100%的数据，n≤32，p≤10e9，c≤10e9，a[i]<p，其中p是质数。