Enormous Product

You are given two integers $l$ and $r$. You need to find the value of

$$\prod_{x=l}^{r}x^{(x+1)}$$

As the value of this equation may be large, you need to find its remainder modulo ($10^9+7$).

Input

The first line will contain an integer $t$ ($1 ≤ t ≤ 5$), the number of test cases.

Each of the next $t$ lines will contain two integers $l$ and $r$ ($1 ≤ l ≤ r ≤ 10^9$).

Output

Find the value of the aforementioned product modulo ($10^9+7$).

Sample

Input	Output
2 1 2 100 100	8 409005006