P3301 [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$ 取模后的答案。

无

无

**【样例解释】** 对于第一组数据，三组解为 $(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\%$ 的数据，$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$。