分数: 466 分
问题陈述
高桥正在开发徒步旅行课程的评估系统。该系统计算每个人的“徒步得分” N 课程编号自 1 to N.
当每门课程的编号以标准十进制表示且不带前导零时,令 k 是位数,让 d_1, d_2, \ldots, d_k 是从左(最高有效数字)到右的数字。由于课程数量至少为 1,我们有 d_1 \geq 1。在这里, d_1, d_2, \ldots, d_k 被视为海拔(之间的整数 0 和 9,包括)第 1 部分、第 2 部分,……, k分别是课程的第节。每条路线都模拟一条山路,数字序列代表海拔的变化。
远足分数定义如下。
首先, 基本分数 B 定义为所有相邻截面对之间的绝对高差之和。也就是说,
B = \sum_{i=1}^{k-1} |d_i - d_{i+1}|
当课程编号只有 1 数字 (k = 1),没有成对的相邻部分,所以 B = 0.
接下来,如果其中至少有一个部分 d_1, d_2, \ldots, d_k 有海拔 0,该球场被认为有“休息点”,基础分数加倍。如果没有剖面有标高 0,基本分数保持不变。
即定义乘数 m as
m = \begin{cases} 2 & (\text{if } 0 \text{ is contained among } d_1, d_2, \ldots, d_k) \\ 1 & (\text{otherwise}) \end{cases}
该路线的徒步得分是 m \times B.
给定一个整数 N 代表路线数量上限,求所有路线的徒步分数总和 N 课程中的课程 1 课程 N,模数 10^9 + 7.
约束
- 1 \leq N \leq 10^{18}
- N 是一个整数
输入
N
- 第一行包含一个整数 N 代表课程数量的上限。
输出
在一行中打印路线中徒步旅行分数的总和 1 课程 N,模数 10^9 + 7.
示例输入 1
15
示例输出 1
12
示例输入 2
20
示例输出 2
42
示例输入 3
1000
示例输出 3
7652
示例输入 4
999999999999999999
示例输出 4
243567135
示例输入 5
1
示例输出 5
0