题目描述

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

给定一个整数 $S$。求满足 $f(l) + f(l + 1) + \cdots + f(r) = S$ 的正整数二元组 $(l,\, r)$（$l \leq r$）的个数，并对 $10^9+7$ 取模后输出。

输入格式

输入按以下格式从标准输入给出。

$S$

输出格式

输出答案。

输入输出样例 #1

输入 #1

1

输出 #1

9

输入输出样例 #2

输入 #2

2

输出 #2

98

输入输出样例 #3

输入 #3

123

输出 #3

460191684

输入输出样例 #4

输入 #4

36018

输出 #4

966522825

输入输出样例 #5

输入 #5

1000

输出 #5

184984484

说明/提示

限制条件

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

样例解释 1

满足条件的 $(l,\, r)$ 组有 $(1,\ 1),\ (2,\ 2),\ \ldots,\ (9,\ 9)$ 共 $9$ 组。

样例解释 2

满足条件的 $(l,\, r)$ 组有 $(1,\ 2)$、$(33,\ 33)$ 等 $98$ 组。