무질서에 순서 매기기

숫자를 나열하면 보통 하나의 수를 뜻하지만, 다르게 해석할 수도 있다. 이 문제에서는 길이가 같은 숫자 나열 사이에 새로운 순서 관계 $\prec$ 를 정의한다.

$n$ 개의 숫자로 이루어진 나열 $s = d_1 d_2 \cdots d_n$ 을 생각하자. 각 $d_i$ $(1 \le i \le n)$ 는 $0$ 부터 $9$ 까지의 숫자 하나다. $\mathrm{sum}(s)$, $\mathrm{prod}(s)$, $\mathrm{int}(s)$ 를 다음과 같이 정의한다.

• $\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)$ 는 나열 $s$ 를 평범하게 십진수로 읽은 정수다.

길이가 같은 두 나열 $s_1$ 과 $s_2$ 에 대해, 다음 세 조건 중 하나를 만족할 때 그리고 그때만 $s_1 \prec s_2$ 이다. 즉 $s_1$ 이 $s_2$ 보다 작다.

1. $\mathrm{sum}(s_1) < \mathrm{sum}(s_2)$
2. $\mathrm{sum}(s_1) = \mathrm{sum}(s_2)$ 이고 $\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)$ 이고 $\mathrm{int}(s_1) < \mathrm{int}(s_2)$

길이가 $2$ 인 나열끼리는 이 순서가 다음과 같이 매겨진다.

$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$

길이가 $n$ 인 나열 $s$ 가 주어진다. 위에서 정의한 순서로 $s$ 보다 작은 길이 $n$ 의 나열이 몇 개인지 세어라.

입력은 한 줄로 주어진다.

d1d2...dn

$n$ 은 $14$ 이하의 양의 정수이고, $d_1, d_2, \ldots, d_n$ 은 각각 $0$ 부터 $9$ 까지의 숫자다. 맨 앞자리가 $0$ 인 나열도 입력으로 주어진다.

위에서 정의한 순서로 $d_1 d_2 \ldots d_n$ 보다 작은 길이 $n$ 의 숫자 나열이 몇 개인지 한 줄에 출력한다.