OI Problems   关于

#0o7ffs. Color

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

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

本题来源于:2014 年 ICPC 亚洲(陕西)西安区域赛 Problem F

nn 朵花,按顺序排成一排。从 mm 种颜色中选出 kk 种颜色,给这 nn 朵花染色,要求相邻的花颜色不同。问共有多少种染色方案?答案对 109+710^9 + 7 取模。

1n,m1091\leq n,m\leq 10^91k1061\leq k\leq 10^6kn,mk\leq n,m


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

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


The first line of the input gives the number of test cases, TT. TT test cases follow. TT is about 300300 and in most cases kk is relatively small.

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


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

3 2 2
3 2 1
Case #1: 2
Case #2: 0