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.

Examples

Input

2


Output

4


Input

654321


Output

968545283
#include<bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7; int f[1000003] , N;

int main(){
	cin >> N; f[0] = f[1] = 1; int sum = 2 , ans = 0;
	for(int i = 2 ; i <= N - 1 ; ++i){f[i] = (sum - f[i - 2] + MOD) % MOD; sum = (sum + f[i]) % MOD;}
	ans = 1ll * f[N - 1] * N % MOD;
	for(int i = N - 2 ; ~i ; --i) ans = (ans + 1ll * f[i] * (1ll * (N - 1) * (N - 1) % MOD + min(N - 1 , i + 2))) % MOD;
	cout << ans; return 0;
}
