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

Let s be a sequence of n digits, d₁d₂···d_n, where each d_i (1 ≤ i ≤ n) is one of 0, 1, . . . , and 9. Let sum(s), prod(s), and int(s) be as follows:

• sum(s) = d₁ + d₂ + · · · + d_n
• prod(s) = (d₁ + 1) × (d₂ + 1) × · · · × (d_n + 1)
• int(s) = d₁ × 10ⁿ⁻¹ + d₂ × 10ⁿ⁻² + · · · + d_n × 10⁰

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

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

1. sum(s₁) < sum(s₂)
2. sum(s₁) = sum(s₂) and prod(s₁) < prod(s₂)
3. sum(s₁) = sum(s₂), prod(s₁) = prod(s₂), and int(s₁) < int(s₂)

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 d₁, d₂, . . . , and d_n is a digit.

출력

Print the number of the n-digit sequences less than d₁d₂···d_n in the order defined above.

제한

힌트