Bringing Order to Disorder

A sequence of digits usually represents a number, but another interpretation is possible. This problem defines a new order relation $\prec$ between digit sequences of the same length.

Let $s = d_1 d_2 \cdots d_n$ be a sequence of $n$ digits, where each $d_i$ $(1 \le i \le n)$ is one of $0, 1, \ldots, 9$. Define $\mathrm{sum}(s)$, $\mathrm{prod}(s)$, and $\mathrm{int}(s)$ as follows.

• $\mathrm{sum}(s) = d_1 + d_2 + \cdots + d_n$
• $\mathrm{prod}(s) = (d_1 + 1) \times (d_2 + 1) \times \cdots \times (d_n + 1)$
• $\mathrm{int}(s) = d_1 \times 10^{n-1} + d_2 \times 10^{n-2} + \cdots + d_n \times 10^0$

$\mathrm{int}(s)$ is the integer that the sequence $s$ represents under the usual decimal reading.

For two sequences $s_1$ and $s_2$ of the same length, $s_1 \prec s_2$ ($s_1$ is less than $s_2$) holds if and only if one of the following three conditions holds.

1. $\mathrm{sum}(s_1) < \mathrm{sum}(s_2)$
2. $\mathrm{sum}(s_1) = \mathrm{sum}(s_2)$ and $\mathrm{prod}(s_1) < \mathrm{prod}(s_2)$
3. $\mathrm{sum}(s_1) = \mathrm{sum}(s_2)$, $\mathrm{prod}(s_1) = \mathrm{prod}(s_2)$, and $\mathrm{int}(s_1) < \mathrm{int}(s_2)$

For sequences of length $2$, the order runs like this.

$00 \prec 01 \prec 10 \prec 02 \prec 20 \prec 11 \prec 03 \prec 30 \prec 12 \prec 21 \prec \cdots \prec 89 \prec 98 \prec 99$

Given a sequence $s$ of $n$ digits, count the sequences of $n$ digits that are less than $s$ under the order $\prec$ defined above.

The input is a single line.

d1d2...dn

$n$ is a positive integer at most $14$, and each of $d_1, d_2, \ldots, d_n$ is a digit from $0$ to $9$. A sequence whose first digit is $0$ can be given.

Print, on a single line, the number of digit sequences of length $n$ that are less than $d_1 d_2 \ldots d_n$ under the order defined above.