시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB54402777.143%

## 문제

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 ≺ among the digit sequences of the same length defined below.

Let s be a sequence of n digits, d1d2···dn, where each di (1 ≤ i ≤ n) is one of 0, 1, . . . , and 9. Let sum(s), prod(s), and int(s) be as follows:

• sum(s) = d1 + d2 + · · · + dn
• prod(s) = (d1 + 1) × (d2 + 1) × · · · × (dn + 1)
• int(s) = d1 × 10n−1 + d2 × 10n−2 + · · · + dn × 100

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

Let s1 and s2 be sequences of the same number of digits. Then s1 ≺ s2 (s1 is less than s2) is satisfied if and only if one of the following conditions is satisfied.

1. sum(s1) < sum(s2)
2. sum(s1) = sum(s2) and prod(s1) < prod(s2)
3. sum(s1) = sum(s2), prod(s1) = prod(s2), and int(s1) < int(s2)

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

00 ≺ 01 ≺ 10 ≺ 02 ≺ 20 ≺ 11 ≺ 03 ≺ 30 ≺ 12 ≺ 21 ≺ · · · ≺ 89 ≺ 98 ≺ 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 ≺ defined above.

## 입력

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

d1d2···dn

n is a positive integer at most 14. Each of d1, d2, . . . , and dn is a digit.

## 출력

Print the number of the n-digit sequences less than d1d2···dn in the order defined above.

## 예제 입력 1

20


## 예제 출력 1

4


## 예제 입력 2

020


## 예제 출력 2

5


## 예제 입력 3

118


## 예제 출력 3

245


## 예제 입력 4

11111111111111


## 예제 출력 4

40073759


## 예제 입력 5

99777222222211


## 예제 출력 5

23733362467675