시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 12 10 5 100.000%

문제

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.

예제 입력

20

예제 출력

4

예제 입력 2

020

예제 출력 2

5

예제 입력 3

118

예제 출력 3

245

예제 입력 4

11111111111111

예제 출력 4

40073759

예제 입력 5

99777222222211

예제 출력 5

23733362467675

힌트