#P11052. [2016杭电多校]A Boring Question

    ID: 10194 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-双射计数乘法原理等比数列求和模逆元费马小定理快速幂

[2016杭电多校]A Boring Question

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 (kj+1kj)=0\binom{k_{j+1}}{k_{j}}=0 while kj+1<kjk_{j+1}<k_{j}. You have to get the answer for each nn and mm that given to you. For example,if n=1n=1,m=3m=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 TT,(1≤T≤10000)(1\le T\le 10000) Then TT lines follow,the i-th line contains two integers nn,mm,(0≤n≤109,2≤m≤109)(0\le n\le 10^9,2\le m\le 10^9)

Output

For each nn and mm,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