非常好的一道数学题，考察了大量数论和组合数学的知识
在做本题之前强烈建议先完成下列两个背景知识：
①：
bzoj 2142礼物
因为本题的一部分数据需要利用到拓展卢卡斯定理，而礼物是拓展卢卡斯定理的裸题，先做礼物是一个比较好的选择
有困难戳这里https://blog.****.net/lleozhang/article/details/82884768
②：
CF451E
本题的核心思想和CF451E完全相同，CF451E稍简单一些，所以先理解这里的思想再做本题会发现难度降了不少
有困难戳这里https://blog.****.net/lleozhang/article/details/83590652
接下来的讨论在你掌握了上两个背景知识的基础上进行：
首先我们注意到一点：他要求方程的解为正整数，那么这样不利于操作，所以我们把m减掉一个n，相当于预设每个x至少为1，然后仅需要求新方程的解非负即可
不要忘记修改上下界
那么这样就可以发现：前面1-n1的要求可以与CF451E完全一致，那么可以使用完全相同的方法来处理。
至于下界的问题：我们可以实现预设所有解均满足下界，那么我们可以再将m减掉所有的下界，这样其他所有x都可以随便选了。
这样就可以用于CF451E完全相同的方法解决掉这道题
可是不要忘记：本题的模数很有特点：
对于40%的数据，模数为10007，这是个质数，直接卢卡斯定理求组合数即可
对于另30%的数据，模数为一个大合数，但是可以质因子分解成几个不同的质数的乘积，那么对每个质数跑卢卡斯，最后中国剩余定理合并即可
对于最后30%的数据，模数为一个大合数，而且质因子分解之后有同一质数的幂次，所以只能使用拓展卢卡斯合并了
// luogu-judger-enable-o2 #include <cstdio>
#define ll long long
int T,p;
int n,m,n1,n2;
int aa[];
int bb[];
ll a[];
ll s[];
ll p0[]={,,,};
ll pu[]={,,,};
ll num[]={,,,};
ll mode[]={,,,,};
ll inv[][];
ll mul[][];
struct node
{
ll mi;
ll val;
};
void init()
{
for(int i=;i<=;i++)
{
inv[][i]=inv[][i]=;
mul[][i]=mul[][i]=;
for(int j=;j<mode[i];j++)
{
inv[j][i]=(mode[i]-mode[i]/j)*inv[mode[i]%j][i]%mode[i];
}
for(int j=;j<mode[i];j++)
{
mul[j][i]=mul[j-][i]*j%mode[i];
inv[j][i]=inv[j-][i]*inv[j][i]%mode[i];
}
}
}
void ex_gcd(ll a,ll b,ll &x,ll &y)
{
if(b==)
{
x=;
y=;
return;
}
ex_gcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-(a/b)*x;
}
ll C(ll x,ll y,int num)
{
if(x<y)
{
return ;
}else if(x==y)
{
return ;
}
if(x<mode[num])
{
return mul[x][num]*inv[y][num]%mode[num]*inv[x-y][num]%mode[num];
}else
{
return C(x%mode[num],y%mode[num],num)*C(x/mode[num],y/mode[num],num)%mode[num];
}
}
ll china()
{
ll M=;
ll ret=;
for(int i=;i<=;i++)
{
ll M0=M/mode[i-];
ll x,y;
ex_gcd(M0,mode[i-],x,y);
x=(x%mode[i-]+mode[i-])%mode[i-];
ret+=x*a[i]%M*M0%M;
ret%=M;
}
return ret;
}
ll solve(ll x,ll y)
{
for(int i=;i<=;i++)
{
a[i]=C(x,y,i-);
}
return china();
}
ll pow_mul(ll x,ll y,ll mod)
{
ll ans=;
while(y)
{
if(y&)
{
ans*=x;
ans%=mod;
}
x*=x;
x%=mod;
y>>=;
}
return ans;
}
ll get_inv(ll a,ll b)
{
ll x,y;
ex_gcd(a,b,x,y);
return (x%b+b)%b;
}
node get_mul(ll x,ll num)
{
if(x==)
{
return (node){,};
}
ll ans=;
ll p1=x/p0[num],p2=x/pu[num];
if(p2)
{
for(ll i=;i<pu[num];i++)
{
if(i%p0[num])
{
ans*=i;
ans%=pu[num];
}
}
ans=pow_mul(ans,p2,pu[num]);
}
for(ll i=pu[num]*p2+;i<=x;i++)
{
if(i%p0[num])
{
ans*=i;
ans%=p;
}
}
node re=get_mul(p1,num);
return (node){re.mi+x,ans*re.val%p};
}
ll get_C(ll x,ll y,ll num)
{
if(x<y)
{
return ;
}else if(x==y)
{
return ;
}
node f1=get_mul(x,num);
node f2=get_mul(y,num);
node f3=get_mul(x-y,num);
ll t1=pow_mul(p0[num],f1.mi-f2.mi-f3.mi,pu[num])*f1.val%pu[num];
ll t2=get_inv(f2.val,pu[num]);
ll t3=get_inv(f3.val,pu[num]);
return t1*t2*t3%pu[num];
}
ll china_again()
{
ll M=p;
ll ret=;
for(int i=;i<=;i++)
{
ll M0=M/pu[i];
ll x,y;
ex_gcd(M0,pu[i],x,y);
x=(x%pu[i]+pu[i])%pu[i];
ret+=x*M0%M*a[i]%M;
if(ret>=M)
{
ret-=M;
}
}
return ret;
}
ll ex_lucas(ll x,ll y)
{
for(int i=;i<=;i++)
{
a[i]=get_C(x,y,i);
}
return china_again();
}
int main()
{
scanf("%d%d",&T,&p);
init();
while(T--)
{
scanf("%d%d%d%d",&n,&n1,&n2,&m);
m-=n;
for(int i=;i<=n1;i++)
{
scanf("%d",&aa[i]);
aa[i]--;
}
for(int i=;i<=n2;i++)
{
scanf("%d",&bb[i]);
bb[i]--;
m-=bb[i];
}
if(m<)
{
printf("0\n");
continue;
}else if(m==)
{
printf("1\n");
continue;
}
if(p==)
{
ll ans=;
for(int i=;i<(<<n1);i++)
{
int t1=m;
int flag=;
for(int j=;j<n1;j++)
{
if((<<j)&i)
{
t1-=(aa[j+]+);
flag=-flag;
}
}
if(t1<)
{
continue;
}
ans+=flag*C(t1+n-,n-,);
ans=(ans%p+p)%p;
}
printf("%lld\n",ans);
}else if(p==)
{
ll ans=;
for(int i=;i<(<<n1);i++)
{
int t1=m;
int flag=;
for(int j=;j<n1;j++)
{
if((<<j)&i)
{
t1-=(aa[j+]+);
flag=-flag;
}
}
if(t1<)
{
continue;
}
ans+=flag*solve(t1+n-,n-);
ans=(ans%p+p)%p;
}
printf("%lld\n",ans);
}else
{
ll ans=;
for(int i=;i<(<<n1);i++)
{
int t1=m;
int flag=;
for(int j=;j<n1;j++)
{
if((<<j)&i)
{
t1-=(aa[j+]+);
flag=-flag;
}
}
if(t1<)
{
continue;
}
ans+=flag*ex_lucas(t1+n-,n-);
if(ans<)
{
ans+=p;
}else if(ans>=p)
{
ans-=p;
}
}
printf("%lld\n",ans);
}
}
return ;
}