Problem C
Office Number
Nathan is a mathematician at a famous university who often sees patterns in the world around him. One day he notices that his office number, which happens to be $224$, has an interesting property: it can be written as a sum of non-negative powers of its digits. In particular, he observes that
\[ 224 = 2^5 + 2^7 + 4^3 \]Nathan wonders what other numbers have this property, and, for any such number, in how many different ways it can be expressed like this. More precisely, if $n$ is a positive integer with base-$10$ digits $d_1 d_2 \ldots d_ k$, where $d_1$ is the most significant digit, he would like to know how many tuples of non-negative integers $(e_1, e_2, \ldots , e_ k)$ there are such that
\[ n = d_1^{e_1} + d_2^{e_2} + \ldots + d_ k^{e_ k} \]For $n=224$, the answer is $2$, since the tuples $(5,7,3)$ and $(7,5,3)$ both work, but no others do.
Nathan has turned to you for help with this challenge. Since $0^ e = 0$ for any positive exponent, and $1^ e = 1$ for any non-negative exponent, you only need to consider numbers with digits in $\{ 2, 3, \ldots , 9\} $. Remember that $p^0 = 1$ for any positive integer, $p$.
Input
The input consists of a single positive integer, $n$, with $1 < n < 10\, 000\, 000$. Each digit of $n$ is between $2$ and $9$, inclusive.
Output
Output a single integer: the number of ways $n$ can be written as a sum of non-negative integer powers of its digits.
| Sample Input 1 | Sample Output 1 |
|---|---|
224 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
225 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
9967749 |
42 |
