All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Given three positive integers N, L and R, find the number of non-decreasing sequences of size at least 1 and at most N, such that each element of the sequence lies between L and R, both inclusive.
Print the answer modulo 106+3.
- First line of input contains T, the number of the test cases.
- Each of next T lines contains three space separated integers N, L and R.
For each test case print the answer modulo 106+3 in a single line.
- 1 ≤ T ≤ 100
- L ≤ R
- Subtask #1 (20 points): 1 ≤ N, L, R ≤ 100
- Subtask #2 (30 points): 1 ≤ N, L, R ≤ 104
- Subtask #3 (50 points): 1 ≤ N, L, R ≤ 109
Input: 2 1 4 5 2 4 5 Output: 2 5
test #1:  and  are the two sequences.
test #2: , , [4, 4], [4, 5] and [5, 5] are the five sequences.
|Tags||april15, combinatorics, darkshadows, dynamic-programming, easy-medium, lucas-theorem, maths|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.