|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||128 MB||49||17||14||30.435%|
The number 729 can be written as a power in several ways: 36, 93 and 272. It can be written as 7291, of course, but that does not count as a power. We want to go some steps further. To do so, it is convenient to use ‘^’ for exponentiation, so we define a^b = ab. The number 256 then can be also written as 2^2^3, or as 4^2^2. Recall that ‘^’ is right associative, so 2^2^3 means 2^(2^3).
We define a tower of powers of height k to be an expression of the form a1^a2^a3^...^ak, with k > 1, and integers ai > 1.
Given a tower of powers of height 3, representing some integer n, how many towers of powers of height at least 3 represent n?
The input file contains several test cases, each on a separate line. Each test case has the form a^b^c, where a, b and c are integers, 1 < a, b, c ≤ 9585.
For each test case, print the number of ways the number n = a^b^c can be represented as a tower of powers of height at least three.
The magic number 9585 is carefully chosen such that the output is always less than 263.
4^2^2 8^12^2 8192^8192^8192 2^900^576
2 10 1258112 342025379