Counting Bounded and Unbounded Positive Integer Solutions

Given the equation \[ x_1 + x_2 + \dots + x_{n} = m \] where \(n = n_1+n_2\), we seek the number of solutions in positive integers under the following constraints:

• For the first \(n_1\) variables, we have an upper bound: \(x_i \le a_i\) for \(i=1,2,\dots, n_1\).
• For the next \(n_2\) variables, we have a lower bound: \(x_i \ge a_i\) for \(i=n_1+1,n_1+2,\dots, n_1+n_2\).

Note that the solutions are counted in positive integers (i.e. each \(x_i\ge1\)).

Transformation: For variables in the second group (with \(x_i\ge a_i\)), define a new variable \(y_i = x_i - (a_i-1)\). Then \(y_i\ge1\) and the equation becomes \[ \sum_{i=1}^{n_1} x_i + \sum_{j=1}^{n_2} y_j = m - \Bigl(\sum_{i=n_1+1}^{n_1+n_2} (a_i-1)\Bigr). \] Denote the new target sum as \(R\): \[ R = m - \Bigl(\sum_{i=n_1+1}^{n_1+n_2} (a_i-1)\Bigr). \] Thus, we need to count the number of solutions to \[ z_1+z_2+\dots+z_{n_1+n_2}= R \] with the conditions:

• For \(i=1,2,\dots,n_1\): \(1 \le z_i \le a_i\).
• For \(j=1,2,\dots,n_2\): \(z_{n_1+j} \ge 1\) (with no upper bound aside from the sum constraint).

If \(R < n_1+n_2\) then there is no valid solution. Since the answer might be very large, output it modulo \(p\).

inputFormat

The input is given in the following format:

n1 n2 m p
a1 a2 ... a_n1
b1 b2 ... b_n2

Here, the first line contains four integers:

• \(n_1\) and \(n_2\): the number of variables in the first and second groups respectively.
• \(m\): the right‐hand side of the equation.
• \(p\): the modulus.

The second line contains \(n_1\) integers \(a_1, a_2, \dots, a_{n_1}\) representing the upper bounds for the first group.

The third line contains \(n_2\) integers \(b_1, b_2, \dots, b_{n_2}\) representing the lower bounds for the second group.

outputFormat

Output a single integer, the number of positive integer solutions satisfying the given conditions, taken modulo \(p\).

sample

1 1 5 100
3
2

3