在字符集大小为$K$的情况下，求长度为$n$且有$m$个互不相同的非空子串的串有多少个？ 由于答案会很大，输出答案对$1000000007(10^9+7)$取模的结果。
输入文件包含多组数据，第一行为数据组数$T$。 接下来的T行，每行有三个正整数$n$ , $m$ , $K$。 $1 \leq T \leq 50,000.$ $1 \leq n \leq 10 ,1 \leq m \leq 100 ,1 \leq K \leq 1,000,000,000.$
对于每组数据，输出答案对$1,000,000,007$ 取模的结果。
3 1 1 1 2 3 3 3 5 8
1 6 168
对于第二个例子，满足要求的串有ab,ac,ba,bc,ca,cb。