只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
3129 - [Sdoi2013]方程
给定方程
X1+X2+. +Xn=M
我们对第l..N1个变量进行一些限制： Xl < = A X2 < = A2 Xn1 < = An1 我们对第n1 + 1..n1+n2个变量进行一些限制： Xn1+l > = An1+1 Xn1+2 > = An1+2 Xnl+n2 > = Anl+n2 求：在满足这些限制的前提下，该方程正整数解的个数。 答案可能很大，请输出对p取模后的答案，也即答案除以p的余数。
输入
输入含有多组数据，第一行两个正整数T，p。T表示这个测试点内的数据组数，p的含义见题目描述。
对于每组数据，第一行四个非负整数n，n1，n2，m。
第二行nl+n2个正整数，表示A1..n1+n2。请注意，如果n1+n2等于0，那么这一行会成为一个空行。
输出
共T行，每行一个正整数表示取模后的答案。
样例
输入
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)
提示
n < = 10^9 , n1 < = 8 , n2 < = 8 , m < = 10^9 ,p<=437367875
对于l00%的测试数据： T < = 5，1 < = A1..n1_n2 < = m，n1+n2 < = n