{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003eProblem E\n\u003c/h2\u003e\n\n\u003cp\u003e\nA 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.\n\u003c/p\u003e\n\n\u003cp\u003e\nLet $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:\u003cbr\u003e\n\u003cbr\u003e\nsum($s$) \u003d $d_1 + d_2 + ... + d_n$\u003cbr\u003e\nprod($s$) \u003d $(d_1 + 1) \\times (d_2 + 1) \\times ... \\times (d_n + 1)$\u003cbr\u003e\nint($s$) \u003d $d_1 \\times 10^{n-1} + d_2 \\times 10^{n-2} + ... + d_n \\times 10^0$\u003cbr\u003e\n\u003cbr\u003e\n\nint($s$) is the integer the digit sequence $s$ represents with normal decimal interpretation.\n\u003c/p\u003e\n\n\u003cp\u003e\nLet $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.\n\u003c/p\u003e\n\n\u003col\u003e\n\u003cli\u003e sum($s_1$) $\u0026lt;$ sum($s_2$)\u003c/li\u003e\n\u003cli\u003e sum($s_1$) $\u003d$ sum($s_2$) and prod($s_1$) $\u0026lt;$ prod($s_2$)\u003c/li\u003e\n\u003cli\u003e sum($s_1$) $\u003d$ sum($s_2$), prod($s_1$) $\u003d$ prod($s_2$), and int($s_1$) $\u0026lt;$ int($s_2$)\u003c/li\u003e\n\u003c/ol\u003e\n\n\u003cp\u003e\nFor 2-digit sequences, for instance, the following relations are satisfied.\u003cbr\u003e\n\u003cbr\u003e\n\n$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$\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\nYour 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.\n\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e\nThe input consists of a single test case in a line.\u003cbr\u003e\n\u003cbr\u003e\n$d_1d_2 ... d_n$\u003cbr\u003e\n\u003cbr\u003e\n\n$n$ is a positive integer at most 14. Each of $d_1, d_2, ...,$ and $d_n$ is a digit.\n\u003c/p\u003e\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cp\u003e\nPrint the number of the $n$-digit sequences less than $d_1d_2 ... d_n$ in the order defined above.\n\u003c/p\u003e\n\n\n\u003ch3\u003eSample Input 1\u003c/h3\u003e\n\n\u003cpre\u003e20\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 1\u003c/h3\u003e\n\n\u003cpre\u003e4\u003c/pre\u003e\n\n\n\n\u003ch3\u003eSample Input 2\u003c/h3\u003e\n\n\u003cpre\u003e020\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 2\u003c/h3\u003e\n\n\u003cpre\u003e5\u003c/pre\u003e\n\n\n\n\u003ch3\u003eSample Input 3\u003c/h3\u003e\n\n\u003cpre\u003e118\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 3\u003c/h3\u003e\n\n\u003cpre\u003e245\u003c/pre\u003e\n\n\n\n\n\u003ch3\u003eSample Input 4\u003c/h3\u003e\n\n\u003cpre\u003e11111111111111\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 4\u003c/h3\u003e\n\n\u003cpre\u003e40073759\u003c/pre\u003e\n\n\n\n\u003ch3\u003eSample Input 5\u003c/h3\u003e\n\n\u003cpre\u003e99777222222211\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 5\u003c/h3\u003e\n\n\u003cpre\u003e23733362467675\u003c/pre\u003e\n"}}]}