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^{100\,000}~

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