Migrated from Lutece 892 Exponential Towers

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

The number $729$ can be written as a power in several ways: $3^6$, $9^3$ and $27^2$. It can be written as $729^1$, 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\verb|^|b = a^b$. 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 $a_1\verb|^|a_2\verb|^|a_3\verb|^|\ldots \verb|^| a_k$, with $k > 1$, and integers $a_i > 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$?

Input

The input file contains several test cases, each on a separate line. Each test case has the form $a\verb|^|b\verb|^|c$, where $a$, $b$ and $c$ are integers, $1 < a, b, c \leq 9585$.

Output

For each test case, print the number of ways the number $n = a\verb|^|b\verb|^|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 $2^{63}$.

Samples

4^2^2
8^12^2
8192^8192^8192
2^900^576

2
10
1258112
342025379

Resources

Northwestern European Regional Contest 2013