Problem Statement

For a positive integer n, let us define f(n) as the number of digits in base 10.
You are given an integer S.
Count the number of the pairs of positive integers $(l, r) (l \leq r)$ such that f(l) + f(l + 1) + ... + f(r) = S, and find the count modulo 10^9 + 7.

Input

Input is given from Standard Input in the following format:
S

Output

Print the answer.

Constraints

• $1 \leq S \leq 10^8$

Sample Input 1

1

Sample Output 1

9

There are nine pairs (l, r) that satisfies the condition: (1, 1), (2, 2), ..., (9, 9).

Sample Input 2

2

Sample Output 2

98

There are 98 pairs (l, r) that satisfies the condition, such as (1, 2) and (33, 33).

Sample Input 3

123

Sample Output 3

460191684

Sample Input 4

36018

Sample Output 4

966522825

Sample Input 5

1000

Sample Output 5

184984484

见题面 Input 部分

见题面 Output 部分