{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThere are an equation.\u003cbr\u003e$\\sum_{0\\leq k_{1},k_{2},\\cdots k_{m} \\leq n} \\prod_{1\\leqslant j \u0026lt;m}\\binom{k_{j+1}}{k_{j}} \\% 1000000007\u003d?$\u003cbr\u003eWe define that $\\binom{k_{j+1}}{k_{j}}\u003d\\frac{k_{j+1}!}{k_{j}!\\left ( k_{j+1}-k_{j} \\right )!}$ . And $\\binom{k_{j+1}}{k_{j}}\u003d0$ while $k_{j+1}\u0026lt;k_{j}$.\u003cbr\u003eYou have to get the answer for each $n$ and $m$ that given to you.\u003cbr\u003eFor example,if $n\u003d1$,$m\u003d3$,\u003cbr\u003eWhen $k_{1}\u003d0,k_{2} \u003d 0,k_{3} \u003d 0,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d1$;\u003cbr\u003eWhen$k_{1}\u003d0,k_{2} \u003d 1,k_{3} \u003d 0,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d0$;\u003cbr\u003eWhen$k_{1}\u003d1,k_{2} \u003d 0,k_{3} \u003d 0,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d0$;\u003cbr\u003eWhen$k_{1}\u003d1,k_{2} \u003d 1,k_{3} \u003d 0,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d0$;\u003cbr\u003eWhen$k_{1}\u003d0,k_{2} \u003d 0,k_{3} \u003d 1,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d1$;\u003cbr\u003eWhen$k_{1}\u003d0,k_{2} \u003d 1,k_{3} \u003d 1,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d1$;\u003cbr\u003eWhen$k_{1}\u003d1,k_{2} \u003d 0,k_{3} \u003d 1,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d0$;\u003cbr\u003eWhen$k_{1}\u003d1,k_{2} \u003d 1,k_{3} \u003d 1,\\binom{k_{2}}{k_{1}}\\binom{k_{3}}{k_{2}}\u003d1$.\u003cbr\u003eSo the answer is 4.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains the only integer $T$,$(1\\le T\\le 10000)$\u003cbr\u003eThen $T$ lines follow,the i-th line contains two integers $n$,$m$,$(0\\le n\\le 10^9,2\\le m\\le 10^9)$\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each $n$ and $m$,output the answer in a single line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1 2\r\n2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n13\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}