Problem 1288
Counting DNAs
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 ≤ im and 1 ≤ jn.

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.

Sample Input
1 2 2
1 2 3
1 3 2
1 3 3
2 2 2
0 0 0
Sample Output
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.

University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).