方程
给定方程
X1+X2+.+Xn=M 我们对第 l⋯N1个变量进行一些限制:
X1≤A1
X2≤A2
...
Xn1≤An1
我们对第 n1+1⋯n1+n2个变量进行一些限制:
Xn1+l≥An1+1
Xn1+2≥An1+2
...
Xn1+n2≥An1+n2
求:在满足这些限制的前提下,该方程正整数解的个数。答案可能很大,请输出对 p 取模后的答案,也即答案除以 p 的余数。
输入含有多组数据。
第一行两个正整数 T,p 。T 表示这个测试点内的数据组数,p 的含义见题目描述。
对于每组数据,第一行四个非负整数 n,n1,n2,m。
第二行 nl+n2个正整数,表示 A1⋯n1+n2。请注意,如果 n1+n2 等于 0,那么这一行会成为一个空行。
其中,n≤109,n1≤8,n2≤8,m≤109,p≤437367875,T≤5,1≤A1⋯n1+n2≤m,n1+n2≤n。
输出共 T 行,每行一个正整数表示取模后的答案。
>输入
3 10007
3 1 1 6
3 3
3 0 0 5
3 1 1 3
3 3
>输出
3
6
0