A Boring Question

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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

Hint

wange2014

Source

2016 Multi-University Training Contest 6

提交代码