#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=1e5+10,M=1e6+10,inf=1e9+10;
const ll INF=1e18+10,mod=2147493647;
ll p[20],a[20];
ll n,m;
ll mulmod(ll x,ll y,ll m)
{
    ll ans=0;
    while(y)
    {
        if(y%2)
        {
            ans+=x;
            ans%=m;
        }
        x+=x;
        x%=m;
        y/=2;
    }
    ans=(ans+m)%m;
    return ans;
}
ll ff(ll x,ll p)
{
    ll ans=1;
    for(int i=1;i<=x;i++)
        ans*=i,ans%=p;
    return ans;
}
ll pow_mod(ll a, ll x, ll p)   {
    ll ret = 1;
    while (x)   {
        if (x & 1)  ret = ret * a % p;
        a = a * a % p;
        x >>= 1;
    }
    return ret;
}

ll Lucas(ll n, ll k, ll p) {       //C (n, k) % p
     ll ret = 1;
     while (n && k) {
        ll nn = n % p, kk = k % p;
        if (nn < kk) return 0;                   //inv (f[kk]) = f[kk] ^ (p - 2) % p
        ret = ret * ff(nn,p) * pow_mod (ff(kk,p) * ff(nn-kk,p) % p, p - 2, p) % p;
        n /= p, k /= p;
     }
     return ret;
}
void exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    ll tmp = x;
    x = y;
    y = tmp - (a / b) * y;
}
ll CRT(ll a[],ll m[],ll n)
{
    ll M = 1;
    ll ans = 0;
    for(ll i=1; i<=n; i++)
        M *= m[i];
    for(ll i=1; i<=n; i++)
    {
        ll x, y;
        ll Mi = M / m[i];
        exgcd(Mi, m[i], x, y);
        //ans = (ans + Mi * x * a[i]) % M;
        ans = (ans +mulmod( mulmod( x , Mi ,M ), a[i] , M ) ) % M;
    }
    ans=(ans + M )% M;
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int k;
        scanf("%lld%lld%d",&n,&m,&k);
        for(int i=1;i<=k;i++)
            scanf("%lld",&p[i]);
        for(int i=1;i<=k;i++)
            a[i]=Lucas(n,m,p[i]);
        printf("%lld\n",CRT(a,p,k));
    }
    return 0;
}