Art Academy VII: A Mysterious Object

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Python 4.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


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


Sample Output 2



There are no comments at the moment.