题目描述

小$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≤10^9，c≤10^9，a[i]<p，其中$p$是质数。

评测数据说明

本题使用按题意独立构造、双实现核对的训练数据，共10个测试点，非原站或官方原始数据。总分100分。