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 j^th nucleotide in i^th 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 i^th 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 ≤ 10⁹)

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.