問題文

正の整数 $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

1

出力例 1

9

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

---

入力例 2

2

出力例 2

98

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

---

入力例 3

123

出力例 3

460191684

---

入力例 4

36018

出力例 4

966522825

---

入力例 5

1000

出力例 5

184984484