SP16686 SOMESUMS - Some Sums

在马里兰大学，迈克尔·香农以深入人心的演讲感动了 Delta Gamma 姐妹会。然而，就在他走出校园时，一名手持武器的数学家截住了他，并定义了一个函数 **f**： $$ f(0, n, k) = n^k \\ f(m, n, k) = \sum_{i=0}^n f(m-1, i, k), \quad m > 0 $$ 这位数学家对香农说：“你必须编写一个程序来计算这个函数的值，并且要对结果取模 $10^9+7$，否则我就开枪！” 事情发生后，数学家因伤入院。一名目击事件的 Sigma Nu 兄弟走到他床边，小声说道：“Martinson 教授，我已经写了一个程序来解决您的问题，但您网站的在线判题系统总是说我答案错了。能告诉我哪里出问题了吗？提交编号是 571972597。” 疲惫的 Martinson 回应道：“你有没有写一个简单的程序来验证在小规模测试下的输出？” Sigma Nu 兄弟走神地说：“你刚才说了什么？我没听清。嗯，你还吃那个布丁吗？”说完，他拿走了教授的巧克力布丁，回家找他的 Zeta 女友共度余生。

输入的第一行为一个整数 **T**，表示有多少个测试用例。接下来的 **T** 行中，每一行包含用空格隔开的三个整数 **m**、**n** 和 **k**。

请输出 **T** 行，每行对应一个测试用例，并给出 **f**(**m**,**n**,**k**) 模 $10^9+7$ 的结果。

- $1 \le T \le 100$ - $0 \le m \le 100$ - $0 \le n \le 100$ - $0 \le k \le 100$ **本翻译由 AI 自动生成**