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 was known other than the fact that his greatest enemy is hewmatt100.
She now hypothesizes:
, where is a subsequence of (represented in base 10), but does not like if appears as a subsequence as well.
likes any integerSome 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) likes, modulo .
Input Specification
The only line of input will contain .
Subtask 1 [10%]
Subtask 2 [90%]
Output Specification
Output how many integers and (inclusive), modulo .
likes betweenSample 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
Comments