UOJ Logo Sharp Sword 剑锋 OI

SSOI

#58. B方程

统计

【问题描述】

给定方程
    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行,每行一个正整数表示取模后的答案

【输入样例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) (1,4,1),(2,3,1)  。
对于第二组 数据 ,六组解为 (1,1,3) ,(1,2,2),(1,3,1) ,(2,1,2) ,(2,2,1),(3,1,1)  。

【时空限制】

2S
256MB

【子任务】

<Markdown

题解参考链接