问题1219--签到题++

1219: 签到题++

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

Miaoyao学习计算机科学小有成果,他决定参加一场程序设计竞赛。可是,他遇到了凉心出题人W。


凉心出题人出了一道“签到题”:
给出一个形如1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4……n n n n n 的序列,即1到n的每个数均依次出现m次,求其中长度为m的本质不同子序列有多少个。答案对\(10^9+7\)取模。

子序列:在数学中,某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列。(源自百度百科)。
本质不同:两个长度为\(m\)的序列A与B不同,当且仅当存在一个位置\(i(1\le i\le m)\)使得\(A_i\ne B_i\)。


输入

一个整数\(T(T\le10000)\),表示数据组数。
接下来\(T\)行,每行两个正整数\(n,m (n,m\le1,000)\)
保证\(\sum n \le100,000,\sum m\le100,000\).

输出

\(T\)行,每行一个整数,表示本质不同的子序列数对\(10^9+7\)取模后的值。

样例输入 Copy

1
2 1

样例输出 Copy

2

提示

\(1\le T\le10000\)
\(1\le n,m\le1,000\)
\(\sum n \le100,000,\sum m\le100,000\).