Time Limit: 1000ms
Memory Limit: 65536kb
Scientists have discovered a new species whose DNA is quite special.
The structure of DNA comprises 2m helical chains each coiled round the same axis. Every chain contains exactly n nucleotides.
Let’s denote the jth nucleotide in ith chain as x(i,j). There are k pairs of nucleotides, denoted as (A,a), (B,b), (C,c), …Any pair of corresponding nucleotides in ith and (i+m)th chains are held tightly together. That means, x(i,j) and x(i+m,j) are always a pair of nucleotides, for any 1 ≤ i ≤ m and 1 ≤ j ≤ n.
Two DNAs A and B are considered same if B can be constructed by rotating A along the axis.
Your task is to to write a program to calculate the number different DNAs.
The input consists of multiple test cases. Each test case contains only three integers n, m and k in a single line, which are explained above. (1 ≤ n,m,k ≤ 109)
The input ends with “0 0 0”.
For each test case, output “Case x: ” first, where x is the test case number. Then output the answer mod 1,000,000,007.
1 2 2 1 2 3 1 3 2 1 3 3 2 2 2 0 0 0
Case 1: 4 Case 2: 9 Case 3: 12 Case 4: 38 Case 5: 16
The 4 different DNAs in test case 1 are: ABab, BAba, AAaa, BBbb.
The 9 different DNAs in test case 2 are: ABab, BAba, ACac, CAca, BCbc, CBcb, AAaa, BBbb, CCcc.