# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Hasinur Is Giving Treat

By Zeronfinity · Limits 4s, 512 MB

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

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).

## Output

For each question, print the answer modulo 1015+37 in a single line.

## Sample

InputOutput
3
3 3
2 3
1 3

6
8
9


### Statistics

17% Solution Ratio

aminulEarliest, Nov '18

rifatrraazzFastest, 0.1s

user.l4zfn7bxLightest, 131 kB

rifatrraazzShortest, 637B