Description

Original source: BZOJ 4403

Given three positive integers $N$, $L$, and $R$, count the number of non-decreasing sequences with lengths between $1$ and $N$, where each element is between $L$ and $R$. Output the result modulo $10^6+3$.

Input Format

The first line of input contains an integer $T$, representing the number of test cases.

Lines $2$ to $T+1$ each contain three integers $N$, $L$, and $R$, with meanings as described in the problem.

Output Format

Output $T$ lines, each containing a single number representing the answer modulo $10^6+3$.

Sample 1

For the first test case, the two valid sequences are $\{4\}$ and $\{5\}$.

2
1 4 5
2 4 5

2
5

Constraints & Hints

For all input, $1\le N,L,R\le 10^9$, $1\le T\le 100$, and it is guaranteed that $L\le R$.