Hasinur wants to give treat. Why? Because, he's been going out with someone new. But Hasinur doesn't want to give treat to everyone. He wants to treat only those who can answer some easy questions for him.
Hasinur will ask you N questions in total. In each question, he will give you a pair of numbers L and R. You will have to answer the sum of factorials of all numbers from L to R, modulo 1015+37 (1000000000000037). Nothing that hard 🙂.
Formally, given M and some queries in the form of L and R, you have to print the following.
$ \sum_{n=L}^R n! modulo 1000000000000037 $
Here, n! means the factorial of n, i.e. $ n! = 1 \times 2 \times 3 \times ... \times (n-1) \times n $
Input starts with two integers N (1 ≤ N ≤ 100), the number of questions.
In the next N lines, each line contains the two integers referring to a question, L (0 ≤ L ≤ 107) and R (L ≤ R ≤ 107).
For each question, print the answer modulo 1015+37 in a single line.
| Input | Output |
|---|---|
3 3 3 2 3 1 3 | 6 8 9 |