配点 : $900$ 点

問題文

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

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

制約

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

入力

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

$S$

出力

答えを出力せよ。

1

9

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

2

98

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

123

460191684

36018

966522825

1000

184984484