# Bringing Order to Disorder

Time Limit : 1 sec, Memory Limit : 262144 KB

## Problem E Bringing Order to Disorder

A sequence of digits usually represents a number, but we may define an alternative interpretation. In this problem we define a new interpretation with the order relation $\prec$ among the digit sequences of the same length defined below.

Let $s$ be a sequence of $n$ digits, $d_1d_2 ... d_n$, where each $d_i$ $(1 \leq i \leq n)$ is one of 0, 1, ... , and 9. Let sum($s$), prod($s$), and int($s$) be as follows:

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

int($s$) is the integer the digit sequence $s$ represents with normal decimal interpretation.

Let $s_1$ and $s_2$ be sequences of the same number of digits. Then $s_1 \prec s_2$ ($s_1$ is less than $s_2$) is satisfied if and only if one of the following conditions is satisfied.

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

For 2-digit sequences, for instance, the following relations are satisfied.

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

Your task is, given an $n$-digit sequence $s$, to count up the number of $n$-digit sequences that are less than $s$ in the order $\prec$ defined above.

### Input

The input consists of a single test case in a line.

$d_1d_2 ... d_n$

$n$ is a positive integer at most 14. Each of $d_1, d_2, ...,$ and $d_n$ is a digit.

### Output

Print the number of the $n$-digit sequences less than $d_1d_2 ... d_n$ in the order defined above.

### Sample Input 1

20

### Sample Output 1

4

### Sample Input 2

020

### Sample Output 2

5

### Sample Input 3

118

### Sample Output 3

245

### Sample Input 4

11111111111111

### Sample Output 4

40073759

### Sample Input 5

99777222222211

### Sample Output 5

23733362467675

Source: ACM International Collegiate Programming Contest , Asia Regional Tsukuba, Tsukuba, Japan, 2015-11-29
http://icpc.iisf.or.jp/2015-tsukuba/