F - Infinite Sequence
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
{{1, ... ,n}} からなる無限長の列 a_1, a_2, ... のうち、 次の条件を満たしているものは何通りあるでしょうか?
- 第 n 項から先はすべて同じ数である。つまり、n \leq i,j ならば a_i = a_j を満たす。
- どの正の整数 i に対しても、第 i 項の直後に並ぶ a_i 個の項はすべて同じ数である。つまり、 i < j < k\leq i+a_i ならば a_j = a_k を満たす。
答えを 10^9+7 で割ったあまりを求めてください。
制約
- 1 \leq n \leq 10^6
- n は整数
入力
入力は以下の形式で標準入力から与えられる。
n
出力
条件を満たす数列の数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
2
出力例 1
4
以下の 4 通りがあります。
- 1, 1, 1, ...
- 1, 2, 2, ...
- 2, 1, 1, ...
- 2, 2, 2, ...
入力例 2
654321
出力例 2
968545283
Score : 1000 points
Problem Statement
How many infinite sequences a_1, a_2, ... consisting of {{1, ... ,n}} satisfy the following conditions?
- The n-th and subsequent elements are all equal. That is, if n \leq i,j, a_i = a_j.
- For every integer i, the a_i elements immediately following the i-th element are all equal. That is, if i < j < k\leq i+a_i, a_j = a_k.
Find the count modulo 10^9+7.
Constraints
- 1 \leq n \leq 10^6
Input
Input is given from Standard Input in the following format:
n
Output
Print how many sequences satisfy the conditions, modulo 10^9+7.
Sample Input 1
2
Sample Output 1
4
The four sequences that satisfy the conditions are:
- 1, 1, 1, ...
- 1, 2, 2, ...
- 2, 1, 1, ...
- 2, 2, 2, ...
Sample Input 2
654321
Sample Output 2
968545283