拓展Lucas+容斥原理
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#define MAXN 10000+10
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define ll long long
#define pb push_back
#define ft first
#define sc second
#define mp make_pair
#define pil pair<int,ll>
#define pll pair<ll,ll>
using namespace std;
struct Lucas{
void extgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=,y=;}
else{
ll xx,yy;
extgcd(b,a%b,xx,yy);
x=yy;
y=xx-a/b*yy;
}
}
ll Inv(ll a,ll b){
ll x,y;
extgcd(a,b,x,y);
x=(x%b+b)%b;
if(!x)x+=b;
return x;
}
ll Pow(ll a,ll b,ll p){
ll ret=1LL;
while(b){
if(b&){(ret*=a)%=p;}
(a*=a)%=p;
b>>=;
}
return ret;
}
ll fac(ll n,ll pi,ll pk){
if(!n)return 1LL;
ll ret=1LL;
for(ll i=;i<pk;i++){
if(i%pi)(ret*=i)%=pk;
}
ret=Pow(ret,n/pk,pk);
for(ll i=;i<=(n%pk);i++){
if(i%pi)(ret*=i)%=pk;
}
return ret*fac(n/pi,pi,pk)%pk;
}
ll C(ll n,ll m,ll pi,ll pk){
ll a=fac(n,pi,pk),b=fac(m,pi,pk),c=fac(n-m,pi,pk);
ll t=0LL;
for(ll i=n/pi;i;i/=pi)t+=i;
for(ll i=m/pi;i;i/=pi)t-=i;
for(ll i=(n-m)/pi;i;i/=pi)t-=i;
ll ret=a*Inv(b,pk)*Inv(c,pk)%pk;
(ret*=Pow(pi,t,pk))%=pk;
return ret;
}
ll n,m,p;
vector<pll> pn;
ll init(ll pp){
p=pp;
ll x=sqrt(pp*1.0);
for(ll i=;i<=x;i++){
if(pp%i==){
ll pk=1LL;
while(pp%i==){
pp/=i;
pk*=i;
}
pn.pb(mp(i,pk));
}
}
if(pp^){
pn.pb(mp(pp,pp));
}
}
ll solve(ll n,ll m){
ll ans=0LL,pi,pk;
for(int i=;i<pn.size();i++){
pi=pn[i].ft,pk=pn[i].sc;
ll t=C(n,m,pi,pk);
(t*=(p/pk))%=p;
(t*=Inv(p/pk,pk))%=p;
(ans+=t)%=p;
}
return ans;
}
}L;
int T,n,n1,n2,m;
int a[];
ll ans,p;
ll calc(ll n,ll m){
return L.solve(m+n-,min(m,n-));
}
void rc(int k,int m,int f){
if(m<)return;
ans+=f*calc(n,m);
ans=(ans%p+p)%p;
for(int i=k+;i<=n1;i++){
rc(i,m-a[i],-f);
}
}
void solve(){
scanf("%d%d%d%d",&n,&n1,&n2,&m);
m-=n;
for(int i=;i<=n1;i++){
scanf("%d",&a[i]);
}
int t;
for(int i=;i<=n2;i++){
scanf("%d",&t);
m-=(t-);
}
if(m<){
printf("0\n");
return;
}
ans=0LL;
rc(,m,);
printf("%lld\n",ans);
}
int main()
{
//freopen("data.in","r",stdin);
scanf("%d%lld",&T,&p);
L.init(p);
while(T--){
solve();
}
return ;
}