原题目：
统计方案
题目描述
小B写了一个程序，随机生成了n个正整数，分别是a[1]…a[n]，他取出了其中一些数，并把它们乘起来之后模p，得到了余数c。但是没过多久，小B就忘记他选了哪些数，他想把所有可能的取数方案都找出来。你能帮他计算一下一共有多少种取数方案吗？请把最后的方案数模1000000007后输出。
小B记得他至少取了一个数。
输入格式：
第一行三个正整数n,p,c，含义如题目所述。
接下来一行有n个正整数，表示生成的n个随机数。
输出格式：
一个数，方案数模1000000007。
样例输入：
3 7 2
1 2 4
样例输出：
2
数据范围：
对于30%的数据，n≤16
另有30%的数据，p≤10000
对于100%的数据，n≤32, p≤10^9, c≤10^9, a[i]<p, p 是质数
前言：由于上次发挥人类智慧居然有人和我一样发挥了，我很生气，所以我又发挥了一次人类智慧。
看到这道题，明显是双向搜索题目。
但是，我们充分发挥人类智慧，由于我们可以利用 \mod p 的乘法性质，将问题转化为动态规划， 因为乘积 \mod p 的结果最多 p 种可能，明显用数组就会爆，所以我们发挥人类机会，没错，哈希表可以解决这个问题。这时，我们再发挥一下人类智慧，可以只维护前一个空间（没错就是滚动优化）。这时速度快的飞起，只需要 O(n \times p) 的时间复杂度就可以做出来，完全可以在 10ms 内解决问题！
PS：如果使用折半搜索，时间复杂度为 O(n\times2^{\frac{n}{2}})。经过与 DP 解法的对比，当 p 达到 2^{16} 后，折半搜索更优。