题目描述

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

输出

9

样例 2

输入

2

输出

98

样例 3

输入

123

输出

460191684

样例 4

输入

36018

输出

966522825

样例 5

输入

1000

输出

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$ 组。

由 ChatGPT 5 翻译