Migrated from Lutece 1449 A Boring Question

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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.

Samples

2
1 2
2 3

3
13

Resources

2016 Multi-University Training Contest 6