## Art Academy VII: A Mysterious Object

View as PDF

Points: 12 (partial)
Time limit: 1.0s
PyPy 2 4.0s
PyPy 3 4.0s
Memory limit: 512M

Author:
Problem type

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 , where is a subsequence of (represented in base 10), but does not like if 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 , help A_L_I_C_E_ find out how many integers between and (inclusive) hewmatt10 likes, modulo .

#### Input Specification

The only line of input will contain .

#### Output Specification

Output how many integers hewmatt10 likes between and (inclusive), modulo .

#### Sample Input 1

200

#### Sample Output 1

19

#### Explanation

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