/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君はハイキングコースの評価システムを開発しています。このシステムでは、1 から N までの番号が付けられた N 個のコースそれぞれについて「ハイキングスコア」を計算します。
各コースの番号を、先頭にゼロを付けない通常の十進表記で書いたとき、その桁数を k、各桁の数字を左（最上位桁）から順に d_1, d_2, \ldots, d_k とします。コース番号は 1 以上なので、d_1 \geq 1 です。このとき、d_1, d_2, \ldots, d_k をそれぞれコースの第 1 区間、第 2 区間、…、第 k 区間の標高（0 以上 9 以下の整数）とみなします。各コースは山道を模しており、桁の数字の並びが標高の変化を表しています。
ハイキングスコアは次のように定義されます。
まず、隣接する区間の標高差の絶対値をすべて足し合わせた値を 基本スコア 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 の区間が 1 つでも含まれている場合、そのコースには「休憩スポット」があるとみなされ、基本スコアが 2 倍されます。標高 0 の区間が 1 つも含まれていない場合、基本スコアはそのままです。
すなわち、倍率 m を
m = \begin{cases} 2 & (d_1, d_2, \ldots, d_k \text{ の中に } 0 \text{ が含まれる場合}) \\ 1 & (\text{それ以外の場合}) \end{cases}
と定めたとき、そのコースのハイキングスコアは m \times B です。
コースの番号の上限を表す整数 N が与えられたとき、コース 1 からコース N までの N 個のコースすべてのハイキングスコアの総和を 10^9 + 7 で割った余りを求めてください。
制約
- 1 \leq N \leq 10^{18}
- N は整数である
入力
N
- 1 行目には、コース番号の上限を表す整数 N が与えられる。
出力
コース 1 からコース N までのハイキングスコアの総和を 10^9 + 7 で割った余りを 1 行で出力せよ。
入力例 1
15
出力例 1
12
入力例 2
20
出力例 2
42
入力例 3
1000
出力例 3
7652
入力例 4
999999999999999999
出力例 4
243567135
入力例 5
1
出力例 5
0
Score : 466 pts
Problem Statement
Takahashi is developing an evaluation system for hiking courses. This system calculates a "hiking score" for each of the N courses numbered from 1 to N.
When the number of each course is written in standard decimal notation without leading zeros, let k be the number of digits, and let d_1, d_2, \ldots, d_k be the digits from left (most significant digit) to right. Since the course number is at least 1, we have d_1 \geq 1. Here, d_1, d_2, \ldots, d_k are regarded as the elevations (integers between 0 and 9, inclusive) of the 1st section, 2nd section, …, k-th section of the course, respectively. Each course simulates a mountain trail, and the sequence of digits represents the changes in elevation.
The hiking score is defined as follows.
First, the base score B is defined as the sum of the absolute differences in elevation between all pairs of adjacent sections. That is,
B = \sum_{i=1}^{k-1} |d_i - d_{i+1}|
When the course number has only 1 digit (k = 1), there are no pairs of adjacent sections, so B = 0.
Next, if at least one section among d_1, d_2, \ldots, d_k has elevation 0, the course is considered to have a "rest spot," and the base score is doubled. If no section has elevation 0, the base score remains as is.
That is, defining the multiplier 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}
the hiking score of that course is m \times B.
Given an integer N representing the upper limit of course numbers, find the sum of hiking scores of all N courses from course 1 to course N, modulo 10^9 + 7.
Constraints
- 1 \leq N \leq 10^{18}
- N is an integer
Input
N
- The first line contains an integer N representing the upper limit of course numbers.
Output
Print in one line the sum of hiking scores from course 1 to course N, modulo 10^9 + 7.
Sample Input 1
15
Sample Output 1
12
Sample Input 2
20
Sample Output 2
42
Sample Input 3
1000
Sample Output 3
7652
Sample Input 4
999999999999999999
Sample Output 4
243567135
Sample Input 5
1
Sample Output 5
0