#0o7ffs. Color

时间限制：6 s       空间限制：256 MiB       标签： 数学 组合数学 容斥原理 组合计数 ICPC 陕西 2014 

算法难度等级：3       思维难度等级：4       实现难度等级：4

$n$ 朵花，按顺序排成一排。从 $m$ 种颜色中选出 $k$ 种颜色，给这 $n$ 朵花染色，要求相邻的花颜色不同。问共有多少种染色方案？答案对 $10^9 + 7$ 取模。

$1\leq n,m\leq 10^9$，$1\leq k\leq 10^6$，$k\leq n,m$。

Description

Recently, Mr. Big recieved $n$ flowers from his fans. He wants to recolor those flowers with $m$ colors. The flowers are put in a line. It is not allowed to color any adjacent flowers with the same color. Flowers $i$ and $i + 1$ are said to be adjacent for every $i$, $1\leq i < n$. Mr. Big also wants the total number of different colors of the $n$ flowers being exactly $k$.

Two ways are considered different if and only if there is at least one flower being colored with different colors.

Input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. $T$ is about $300$ and in most cases $k$ is relatively small.

For each test case, there will be one line, which contains three integers $n, m, k$ ($1 \leq n, m \leq 10^9$, $1 \leq k \leq 10^6$, $k \leq n, m$).

Output

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the number of ways of different coloring methods modulo $10^9 + 7$.

2
3 2 2
3 2 1

Case #1: 2
Case #2: 0