题目描述

对于一个正整数 $n$，我们定义 $f(n)$ 为十进制下的位数。

给定一个整数 $S$。计算满足条件 $f(l) + f(l + 1) + ... + f(r) = S$ 的正整数对 $(l, r)$ ($l \leq r$) 的数量，并将结果取模 $10^9 + 7$。

约束条件

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

---

输入

从标准输入读取输入。数据格式如下：

$S$

输出

输出答案。

---

示例输入 1

1

示例输出 1

9

满足条件的正整数对 $(l, r)$ 有九个：$(1, 1)$, $(2, 2)$, $...$, $(9, 9)$。

---

示例输入 2

2

示例输出 2

98

满足条件的正整数对 $(l, r)$ 有 $98$ 个，例如 $(1, 2)$ 和 $(33, 33)$。

---

示例输入 3

123

示例输出 3

460191684

---

示例输入 4

36018

示例输出 4

966522825

---

示例输入 5

1000

示例输出 5

184984484