How Many Bases?

Input: Standard Input

Output: Standard Output

A classical problem of number theory is “Find the number of trailing zeroes in N^M, in base B”. This problem is quite conventional and easy. But a number can have same number of trailing zeroes in more than one base. For example, if decimal number 24 is written in 3, 4, 6, 8, 12 and 24 based number system, it will look like 80, 60, 40, 30, 20 and 10 respectively. So in all number systems it has only one trailing zero. Given a number N^M, your job is to find out the number of integer bases in which it has exactly T trailing zeroes.

Input

The input file contains at most 10000 line of input. Each line contains three integers N (1 ≤ N ≤ 10⁸), M (0< M≤ 10⁷) and T (0< T ≤ 10⁴). The meaning of N, M and T is given in the problem statement. Input is terminated by a line containing three zeroes, which obviously should not be processed for calculation.

Output

For each line of input produce one line of output. This line contains the serial of output followed by an integer NB, which is modulo 100000007 value of number of bases in which N^M has exactly T trailing zeroes.

Sample Input Output for Sample Input

24 1 1

100 200 10

23 18 2

0 0 0

Case 1: 6

Case 2: 312

Case 3: 3

Problemsetter: Shahriar Manzoor, Special Thanks: Derek Kisman