SP22766 MSET - Make Sets
Description
For a given number **N** you have **K** copies of each number from 1 to N. Therefore, you have a total of **N\*K** numbers. You need to form **M** sets **s1 ,s2 ,s3 , .... sm** where a set should contain unique numbers(set may be empty).
Now, let D be the sum of size of all M sets.(where the size of a set is number of elements in it)
Let **G(i)**= number of ways to form M sets such that D is equal to i.
Find **G(0)+ G(1) +...... G(N\*K)** modulo 10^9 + 7.
Note: Ordering of sets matters as the sets are numbered.
**For eg:**
N=2, M=2, K=2
So, the numbers present initially are (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}
{ } represents empty set.
So answer = G(0)+G(1)+G(2)+G(3)+G(4) = 16
**Input Specification** First line of input consists of integer t denoting number of test cases.
Each of the next t lines contain 3 integers N, M , K where N>=M>=K
**Output Specification** Output consists of t lines. Each line contains the answer modulo 10^9 + 7.
**Constraint**
1
Input Format
N/A
Output Format
N/A