Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Tom was on the way home from school. He saw a matrix in the sky. He found that if we numbered rows and columns of the matrix from 0, then,

${a}_{i,j}=C_{i}^{j}$

if i < j, ${a}_{i,j}=0$

Tom suddenly had an idea. He wanted to know the sum of the numbers in some rectangles. Tom needed to go home quickly, so he wouldn't solve this problem by himself. Now he wants you to help him.

Because the number may be very large, output the answer to the problem modulo a prime p.

${a}_{i,j}=C_{i}^{j}$

if i < j, ${a}_{i,j}=0$

Tom suddenly had an idea. He wanted to know the sum of the numbers in some rectangles. Tom needed to go home quickly, so he wouldn't solve this problem by himself. Now he wants you to help him.

Because the number may be very large, output the answer to the problem modulo a prime p.

Multi test cases(about 8). Each case occupies only one line, contains five integers, ${x}_{1}、{y}_{1}、{x}_{2}、{y}_{2}、p.

{x}_{1}\leq {x}_{2}\leq {10}^{5},{y}_{1}\leq {y}_{2}\leq {10}^{5},2\leq p\leq {10}^{9}$.

You should calculate $\sum_{i={x}_{1}}^{{x}_{2}}\sum_{j={y}_{1}}^{{y}_{2}}{a}_{i,j}$ mod p

{x}_{1}\leq {x}_{2}\leq {10}^{5},{y}_{1}\leq {y}_{2}\leq {10}^{5},2\leq p\leq {10}^{9}$.

You should calculate $\sum_{i={x}_{1}}^{{x}_{2}}\sum_{j={y}_{1}}^{{y}_{2}}{a}_{i,j}$ mod p

提交代码