{"trustable":false,"sections":[{"title":"Statement","value":{"format":"PLAIN","content":"Recently, Mr. Big recieved n owers from his fans. He wants to recolor those owers with m colors. The owers are put in a line. It is not allowed to color any adjacent owers with the same color. Flowers i and i + 1 are said to be adjacent for every i, 1 ≤ i \u003c n. Mr. Big also wants the total number of different colors of the n owers being exactly k.\n\nTwo ways are considered different if and only if there is at least one ower being colored with different colors."}},{"title":"Input","value":{"format":"PLAIN","content":"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.\nFor each test case, there will be one line, which contains three integers n, m, k \n(1 ≤ n, m ≤ 109, 1 ≤ k ≤ 106 , k ≤ n, m )."}},{"title":"Output","value":{"format":"PLAIN","content":"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."}},{"title":"Sample Input","value":{"format":"PLAIN","content":"2\n3 2 2\n3 2 1"}},{"title":"Sample Output","value":{"format":"PLAIN","content":"Case #1: 2\nCase #2: 0"}}]}