Home

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$.

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