Number of Digits

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.

Constraints

• 1 \leq S \leq 10^8

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.

Examples

Input

1

Output

9

Input

2

Output

98

Input

123

Output

460191684

Input

36018

Output

966522825

Input

1000

Output

184984484

inputFormat

Input

Input is given from Standard Input in the following format:

S

outputFormat

Output

Print the answer.

Examples

Input

1

Output

9

Input

2

Output

98

Input

123

Output

460191684

Input

36018

Output

966522825

Input

1000

Output

184984484

样例

1

9