[SDOI2013] 方程

题目描述

给定方程 $x_1+x_2+\dots +x_{n}=m$。 我们对第 $1 \sim n_1$ 个变量进行一些限制: $x_{1} \le a_{1},x_{2} \le a_{2},\dots, x_{n_1} \le a_{n_1}$。 我们对第 $n_1+1\sim n_1+n_2$ 个变量进行一些限制: $x_{n_1+1} \ge a_{n_1+1},x_{n_1+2} \ge a_{n_1+2},\dots,x_{n1+n2} \ge a_{n_1+n_2}$。 求:在满足这些限制的前提下,该方程正整数解的个数。答案可能很大,请输出对 $p$ 取模后的答案。

输入输出格式

输入格式


输入含有多组数据。 第一行两个正整数 $T,p$。$T$ 表示这个测试点内的数据组数,$p$ 的含义见题目描述。 对于每组数据,第一行四个非负整数 $n,n_1,n_2,m$。 第二行 $n_1+n_2$ 个正整数,表示 $a_{1},a_2,\dots, a_{n_1+n_2}$。请注意,如果 $n_1+n_2$ 等于 $0$,那么这一行会成为一个空行。

输出格式


共 $T$ 行,每行一个正整数表示取模后的答案。

输入输出样例

输入样例 #1

3 10007
3 1 1 6
3 3
3 0 0 5

3 1 1 3
3 3

输出样例 #1

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)$。 ![](https://cdn.luogu.com.cn/upload/pic/17621.png) 对于 $100\%$ 的数据,$1\le T \le 5$,$1\le m, n \le 10^9$,$1 \le a_i \le m$,$0 \le n_1,n_2 \le \min(8, m)$ 且 $n_1 + n_2 \le n$,$1\le p \le 437367875$。