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

见题面

见题面