hewmatt10 has been captured!

After his army was defeated and his bunker discovered, he was found protecting a mysterious, password-protected box. A_L_I_C_E_'s interest now piqued, she decides to try and open it. Not much about hewmatt10 was known other than the fact that his greatest enemy is hewmatt100.

She now hypothesizes:

hewmatt10 likes any integer $X$, where $10$ is a subsequence of $X$ (represented in base 10), but does not like $X$ if $100$ appears as a subsequence as well.

Some numbers which he likes are 10, 180, 817909, and 4041404.

Some numbers he does not like are 100, 10000, 2, 1800, and 8081709005.

Given an integer $K$, help A_L_I_C_E_ find out how many integers between $0$ and $K$ (inclusive) hewmatt10 likes, modulo ${10}^9+7$.

Input Specification

The only line of input will contain $K$.

Subtask 1 [10%]

$1\le K\le {10}^6$

Subtask 2 [90%]

$1\le K\le {10}^{100000}$

Output Specification

Output how many integers hewmatt10 likes between $0$ and $K$ (inclusive), modulo ${10}^9+7$.

Sample Input 1

200

Sample Output 1

19

Explanation for Sample Output 1

The 19 numbers are 10, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 120, 130, 140, 150, 160, 170, 180, and 190.

Sample Input 2

10000

Sample Output 2

486