← 返回题目列表

AtCoder · awc0043_e

E. 山路徒步得分

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

分数: 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