A classical problem of number theory is “Find the number of trailing zeroes in NM, 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 NM, your job is to find out the number of integer bases in which it has exactly T trailing zeroes.
The input file contains at most 10000 line of input. Each line contains three integers N (1 ≤ N ≤ 108), M (0< M≤ 107) and T (0< T ≤ 104). 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.
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 NM has exactly T trailing zeroes.
24 1 1 100 200 10 23 18 2 0 0 0
Case 1: 6 Case 2: 312 Case 3: 3
Migrated from old NTUJ.
icpc regional 2009, dhaka site
| No. | Testdata Range | Score |
|---|