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

输入格式：

第一行三个正整数n,p,c，含义如题目所述。
接下来一行有n个正整数，表示生成的n个随机数。

输出格式：

一个数，方案数模1000000007。

样例输入：

2 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是质数

时间限制：

1 sec

空间限制：

128MB

#include <bits/stdc++.h>

#define mod 1000000007

#define ll long long

using namespace std;

ll n,p,c,a[1000],tot,ans;

vector <ll> s;

vector <pair<ll,ll> > t;

ll m_pow(ll a,ll b)//快速幂，求逆元

{

    ll ans=1;

    while (b)

    {

        if (b&1)

          ans=(ans*a)%p;

        b>>=1;

        a=(a*a)%p;

    }

    return ans;

}

void dfs1(ll x,ll l,ll r,ll sum)//用dfs求出每一个乘积

{

    if (x==r+1)

    {

        ll ne;

        ne=(m_pow(sum,p-2)*c)%p;//将每一乘积需要的答案压入数组

        s.push_back(ne);

        return;

    }

    dfs1(x+1,l,r,sum);

    dfs1(x+1,l,r,(sum*a[x])%p);

}

void dfs2(ll x,ll l,ll r,ll sum)

{

    if (x==r+1)

    {

        vector <pair<ll,ll> > :: iterator it;

        it=lower_bound(t.begin(),t.end(),make_pair(sum,(ll)0));//进行匹配

        if ((*it).first==sum)

          ans=(ans+(*it).second)%mod;

        return;

    }

    dfs2(x+1,l,r,sum);

    dfs2(x+1,l,r,(sum*a[x])%p);

}

int main()

{

    scanf("%lld%lld%lld",&n,&p,&c);

    for (ll i=1;i<=n;i++)

      scanf("%lld",&a[i]);

    if (c>=p)

    {

        printf("0\n");

        return 0;

    }

    for (ll i=1;i<=n;i++)

      a[i]%=p;

    dfs1(1,1,n/2,1);

    sort(s.begin(),s.end());

    ll kind=s[0],w=1;

    for (ll i=1;i<(ll)s.size();i++)

    {

        if (s[i]==kind)

          w++;

        else

        {

            t.push_back(make_pair(kind,w));

            w=1;

            kind=s[i];

        }

    }

    t.push_back(make_pair(kind,w));

    tot=0;

    dfs2(n/2+1,n/2+1,n,1);

    if (c==1)

      ans=(ans-1)%mod;

    printf("%lld\n",ans%mod);

}