[SDOI2013]方程
题号：NC20358
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定方程
X1+X2+. +Xn=M
我们对第1..N1个变量进行一些限制：
X1< = A
X2 < = A2
Xn1 < = An1
我们对第n1 + 1..n1+n2个变量进行一些限制：
Xn1+1> = An1+1
Xn1+2 > = An1+2
Xn1+n2 > = Anl+n2
求：在满足这些限制的前提下，该方程正整数解的个数。
答案可能很大，请输出对p取模后的答案，也即答案除以p的余数。

输入描述:

输入含有多组数据，第一行两个正整数T，p。
T表示这个测试点内的数据组数，p的含义见题目描述。     
对于每组数据，第一行四个非负整数n，n1，n2，m。     
第二行n1+n2个正整数，表示A1..n1+n2。请注意，如果n1+n2等于0，那么这一行会成为一个空行。

输出描述:

共T行，每行一个正整数表示取模后的答案。
示例1

输入

复制 
3 10007
3 1 1 6
3 3
3 0 0 5

3  1  1  3
3  3

输出

复制 
3
6
0

说明

【样例说明】
对于第一组数据，三组解为(1，3，2)，(1,4,1),(2,3,1)
对于第二组数据，六组解为(1，1，3)，(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)

备注:


对于100%的测试数据：