SP22766 MSET - Make Sets
题目描述
给定一个整数 **N**，你拥有从 1 到 N 的每个数字的 **K** 个副本。也就是说，你总共有 **N\*K** 个数字。现在需要将这些数字分成 **M** 个集合 **s1, s2, s3, ..., sm**。每个集合中的数字必须唯一，一个数字不能在同一个集合中出现多次（集合可以为空）。
我们定义 D 为所有 M 个集合中元素数量的总和，也就是说，D 是这些集合“大小”的总和。
接下来，我们定义 **G(i)** 表示能够构造出 M 个集合并且使得此时总和 D 等于 i 的方案数。
需要计算 **G(0) + G(1) + ... + G(N\*K)**，并将结果对 10^9 + 7 取模。
注意：集合的顺序是重要的，因为集合本身是经过编号的。
**举个例子：**
当 N=2, M=2, K=2 时，
初始数字为 (1, 1, 2, 2)
- G(0)=1,
即两集合都��空 { }, { }。
- G(1)=4,
可能的方案包括：
{1}, { }
{2}, { }
{ }, {1}
{ }, {2}
- G(2)=6,
可能的方案包括：
{1}, {2}
{2}, {1}
{1}, {1}
{2}, {2}
{1,2}, { }
{ }, {1,2}
- G(3)=4,
可能的方案包括：
{1,2}, {1}
{1,2}, {2}
{1}, {1,2}
{2}, {1,2}
- G(4)=1,
唯一的方案：
{1,2}, {1,2}
其中 { } 表示空集合。
所以，答案为 G(0) + G(1) + G(2) + G(3) + G(4) = 16。
输入格式
第一行输入一个整数 t，表示测试用例的数量。
接下来的 t 行，每行输入三个整数 N, M, K，其中 N ≥ M ≥ K。
输出格式
输出共 t 行，每行包含一个整数，为对应测试用例的答案，对 10^9 + 7 取模。
说明/提示
1 ≤ t ≤ 100
1 ≤ M ≤ N ≤ 100000
0 ≤ K ≤ M
```
样例输入
3
2 2 2
4 3 1
3 1 1
样例输出
16
256
8
```
**本翻译由 AI 自动生成**