{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"在遥远的卢克尼卡王国,有个传奇人物----菜月昴。一天他受罗兹瓦尔公爵委托,对一面由1*n的大型石块组成墙体进行喷漆工作,并且要求墙体最后恰好具有k种颜色。因为他非常不喜欢两块相邻石块的颜色相同(比如某两块相邻石块颜色为粉红与粉红或蓝与蓝),所以他会特意去避免这种情况。现在有m种颜色漆料,菜月昂想要知道有多少种喷漆方案,你能帮助他吗?\n\n**Input**\n\n第一行输入一个正整数T(1\u003c\u003dT\u003c\u003d300),表示样例组数。\n\n对于每组样例输入一行三个正整数n, m, k(1\u003c\u003dn,m\u003c\u003d10^9, 1\u003c\u003dk\u003c\u003d10^6)。\n\n**Output**\n\n对于每个样例输出一行`Case #x: y`,其中x表示测试样例号(从1开始),y表示方案数,方案数可能很大,所以对1000000007取模"}},{"title":"Sample Input","value":{"format":"MD","content":"2\n3 2 2\n3 2 1"}},{"title":"Sample Output","value":{"format":"MD","content":"Case #1: 2\nCase #2: 0"}}]}