Find the number of solutions, the equation ∑Xi
= s have, if Ai≤Xi≤Bi for
each i = 1…n.
For example,
X1 + X2 + X3 = 10
-1 ≤X1 ≤ 3
2 ≤ X2≤ 4
6 ≤ X3≤ 7
The above set of equations has 6 solutions. They are: {1,4,7},
{0,3,7}, {0,4,6}, {1,2,7}, {1,3,6} and {2,2,6}.
You are given n the number of variables and the range
of them. Your task is to calculate the number of solutions of that equation.
First line of the Input contains T (≤20000) the
number of test cases. Then T test cases follow. First line of each test
case contains 2 integer n (1≤n≤8) and s (-50000 ≤ s
≤ 50000). Next n lines each
contain 2 integers describing the range of each variable. The ith
line Ai and Bi (‑10000 ≤ Ai
≤ Bi ≤10000). Xi can take any
integral value in the range [Ai, Bi].
For each test case output contains one integer denoting the
number of solutions of the given equations. Output the value modulo 200003.
1 3 10 -1 3 2 4 6 7
6
Migrated from old NTUJ.
uva11266
| No. | Testdata Range | Score |
|---|