← 返回题目列表

AtCoder · arc090_d

F. 位数

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

对于正整数 n,让我们定义 f(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).


示例输入 2

2

示例输出 2

98

有 98 对 (l, r) 满足条件,例如 (1, 2) 和 (33, 33).


示例输入 3

123

示例输出 3

460191684

示例输入 4

36018

示例输出 4

966522825

示例输入 5

1000

示例输出 5

184984484