题目描述

正の整数 $n$ に対し、$f(n)$ を $n$ の $10$ 進法での桁数と定めます。

整数 $S$ が与えられます。 正の整数の組 $(l,\ r)$ ($l\ \leq\ r$) であって、$f(l)\ +\ f(l\ +\ 1)\ +\ ...\ +\ f(r)\ =\ S$ を満たすものの個数を $10^9\ +\ 7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$

输出格式

答えを出力せよ。

题目大意

对于一个正整数 $n$，设 $f(n)$ 表示它在十进制下的位数。如：$f(1234)=4, f(33)=2, f(101)=3$。给定 $k\ (k\le 10^8)$ ，求正整数对 $(l,r)\ (l\le r)$ 的个数，使得$\sum_{i=l}^{r} f(i)=k$。例子：当 $k=1$时，有九组：$(1,1),(2,2),...,(9,9)$。答案对 $10^9+7$ 取模。

1

9

2

98

123

460191684

36018

966522825

1000

184984484

提示

制約

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

Sample Explanation 1

条件を満たす $(l,\ r)$ の組は $(1,\ 1)$, $(2,\ 2)$, $...$, $(9,\ 9)$ の $9$ 個あります。

Sample Explanation 2

条件を満たす $(l,\ r)$ の組は $(1,\ 2)$ や $(33,\ 33)$ など $98$ 個あります。