A Boring Question

Problem Description

There are an equation. $\sum_{0\leq k_{1},k_{2},\cdots k_{m} \leq n} \prod_{1\leqslant j <m}\binom{k_{j+1}}{k_{j}} \% 1000000007=?$ We define that $\binom{k_{j+1}}{k_{j}}=\frac{k_{j+1}!}{k_{j}!\left ( k_{j+1}-k_{j} \right )!}$ . And $\binom{k_{j+1}}{k_{j}}=0$ while $k_{j+1}<k_{j}$. You have to get the answer for each $n$ and $m$ that given to you. For example,if $n=1$,$m=3$, When $k_{1}=0,k_{2} = 0,k_{3} = 0,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=1$; When$k_{1}=0,k_{2} = 1,k_{3} = 0,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=0$; When$k_{1}=1,k_{2} = 0,k_{3} = 0,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=0$; When$k_{1}=1,k_{2} = 1,k_{3} = 0,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=0$; When$k_{1}=0,k_{2} = 0,k_{3} = 1,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=1$; When$k_{1}=0,k_{2} = 1,k_{3} = 1,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=1$; When$k_{1}=1,k_{2} = 0,k_{3} = 1,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=0$; When$k_{1}=1,k_{2} = 1,k_{3} = 1,\binom{k_{2}}{k_{1}}\binom{k_{3}}{k_{2}}=1$. So the answer is 4.

Input

The first line of the input contains the only integer $T$,$(1\le T\le 10000)$ Then $T$ lines follow,the i-th line contains two integers $n$,$m$,$(0\le n\le 10^9,2\le m\le 10^9)$

Output

For each $n$ and $m$,output the answer in a single line.

Sample Input

2
1 2
2 3

Sample Output

3
13

Author

UESTC

Source

2016 Multi-University Training Contest 6