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