#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long int
#define mod 1000000009
using namespace std;
ll pow1(ll a,ll b)
{
ll z;
if(b==0)
return 1;
z=pow1(a,b/2)%mod;
z=(z*z)%mod;
if(b%2==1)
z=(z*a)%mod;
return z;
}
ll abs1(ll x)
{
if(x<0)
return -x;
return x;
}
ll min1(ll a,ll b)
{
return a<b?a:b;
}
ll max1(ll a,ll b)
{
return a<b?b:a;
}
ll fact[100005],in_fact[100005];
ll factorial()
{
ll i,j,k,l,m,n;
fact[0]=1;
in_fact[0]=1;
for(i=1;i<=100000;i++)
{
fact[i]=(i*fact[i-1])%mod;
in_fact[i]=pow1(fact[i],mod-2);
}
}
int main()
{
factorial();
int t;
scanf("%d",&t);
while(t--)
{
ll i,j,k,m,n,temp,q,query;
scanf("%lld %lld",&n,&q);
ll arr[100005]={0};
for(i=0;i<n;i++)
{
scanf("%lld",&arr[i]);
}
for(query=0;query<q;query++)
{
ll fr[105]={0},temp2;
scanf("%lld",&m);
for(i=0;i<n;i++)
{
if(arr[i]<0)
{
temp=abs1(arr[i]);
temp=temp/m;
temp++;
temp2=((temp)*m+arr[i])%m;
}
else
{
temp2=arr[i]%m;
}
fr[temp2]++;
}
ll dp[105][105]={{0}};
dp[0][0]=1;
dp[0][0]=1;
for(i=0;i<m;i++)
{
temp=min(m,fr[i]);
for(j=1;j<=temp;j++)
{
ll no;
no=(j*i)%m;
ll temp3=0,l;
for(l=j;l<=fr[i];l=l+m)
temp3=(temp3+ (((fact[fr[i]]*in_fact[l])%mod)*in_fact[fr[i]-l])%mod )%mod;
for(k=0;k<m;k++)
{
dp[i+1][k]=(dp[i+1][k]+(dp[i][(m+k-no)%m]*temp3)%mod)%mod;
}
}
for(k=0;k<m;k++)
dp[i+1][k]=(dp[i+1][k]+dp[i][k])%mod;
}
printf("%lld\n",dp[m][0]);
}
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxjbWF0aD4KI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CiNkZWZpbmUgbW9kIDEwMDAwMDAwMDkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpsbCBwb3cxKGxsIGEsbGwgYikKewogICAgbGwgejsKICAgIGlmKGI9PTApCiAgICAgICAgcmV0dXJuIDE7CiAgICB6PXBvdzEoYSxiLzIpJW1vZDsKICAgIHo9KHoqeiklbW9kOwogICAgaWYoYiUyPT0xKQogICAgICAgIHo9KHoqYSklbW9kOwogICAgcmV0dXJuIHo7Cn0KCmxsIGFiczEobGwgeCkKewogICAgaWYoeDwwKQogICAgICAgIHJldHVybiAteDsKICAgIHJldHVybiB4Owp9CgpsbCBtaW4xKGxsIGEsbGwgYikKewogICAgICByZXR1cm4gYTxiP2E6YjsKfQoKbGwgbWF4MShsbCBhLGxsIGIpCnsKICAgICAgcmV0dXJuIGE8Yj9iOmE7Cn0KCmxsIGZhY3RbMTAwMDA1XSxpbl9mYWN0WzEwMDAwNV07CgpsbCBmYWN0b3JpYWwoKQp7CiAgICBsbCBpLGosayxsLG0sbjsKICAgIGZhY3RbMF09MTsKICAgIGluX2ZhY3RbMF09MTsKICAgIGZvcihpPTE7aTw9MTAwMDAwO2krKykKICAgIHsKICAgICAgICBmYWN0W2ldPShpKmZhY3RbaS0xXSklbW9kOwogICAgICAgIGluX2ZhY3RbaV09cG93MShmYWN0W2ldLG1vZC0yKTsKICAgIH0KCn0KCgoKaW50IG1haW4oKQp7CiAgICBmYWN0b3JpYWwoKTsKICAgIGludCB0OwogICAgc2NhbmYoIiVkIiwmdCk7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgbGwgaSxqLGssbSxuLHRlbXAscSxxdWVyeTsKICAgICAgICBzY2FuZigiJWxsZCAlbGxkIiwmbiwmcSk7CgogICAgICAgIGxsIGFyclsxMDAwMDVdPXswfTsKICAgICAgICBmb3IoaT0wO2k8bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBzY2FuZigiJWxsZCIsJmFycltpXSk7CiAgICAgICAgfQogICAgICAgIGZvcihxdWVyeT0wO3F1ZXJ5PHE7cXVlcnkrKykKICAgICAgICB7CiAgICAgICAgICAgIGxsIGZyWzEwNV09ezB9LHRlbXAyOwogICAgICAgICAgICBzY2FuZigiJWxsZCIsJm0pOwogICAgICAgICAgICBmb3IoaT0wO2k8bjtpKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKGFycltpXTwwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHRlbXA9YWJzMShhcnJbaV0pOwogICAgICAgICAgICAgICAgICAgIHRlbXA9dGVtcC9tOwogICAgICAgICAgICAgICAgICAgIHRlbXArKzsKICAgICAgICAgICAgICAgICAgICB0ZW1wMj0oKHRlbXApKm0rYXJyW2ldKSVtOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHRlbXAyPWFycltpXSVtOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZnJbdGVtcDJdKys7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGxsIGRwWzEwNV1bMTA1XT17ezB9fTsKCiAgICAgICAgICAgIGRwWzBdWzBdPTE7CiAgICAgICAgICAgIGRwWzBdWzBdPTE7CiAgICAgICAgICAgIGZvcihpPTA7aTxtO2krKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdGVtcD1taW4obSxmcltpXSk7CiAgICAgICAgICAgICAgICBmb3Ioaj0xO2o8PXRlbXA7aisrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGxsIG5vOwogICAgICAgICAgICAgICAgICAgIG5vPShqKmkpJW07CiAgICAgICAgICAgICAgICAgICAgbGwgdGVtcDM9MCxsOwogICAgICAgICAgICAgICAgICAgIGZvcihsPWo7bDw9ZnJbaV07bD1sK20pCiAgICAgICAgICAgICAgICAgICAgICAgIHRlbXAzPSh0ZW1wMysgKCgoZmFjdFtmcltpXV0qaW5fZmFjdFtsXSklbW9kKSppbl9mYWN0W2ZyW2ldLWxdKSVtb2QgICklbW9kOwogICAgICAgICAgICAgICAgICAgIGZvcihrPTA7azxtO2srKykKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGRwW2krMV1ba109KGRwW2krMV1ba10rKGRwW2ldWyhtK2stbm8pJW1dKnRlbXAzKSVtb2QpJW1vZDsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CgoKCiAgICAgICAgICAgICAgICBmb3Ioaz0wO2s8bTtrKyspCiAgICAgICAgICAgICAgICAgICAgZHBbaSsxXVtrXT0oZHBbaSsxXVtrXStkcFtpXVtrXSklbW9kOwogICAgICAgICAgICB9CgoKICAgICAgICAgICAgcHJpbnRmKCIlbGxkXG4iLGRwW21dWzBdKTsKICAgICAgICB9CiAgICB9CgoKICAgIHJldHVybiAwOwp9Cg==