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<stdio.h>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const int MX = 1000005;
const int MM = 1000000007;

char A[MX], B[MX];
ll X[MX], Y[MX];
int N;

int main()
{
	scanf("%d", &N);
	X[0] = Y[0] = 1; X[1] = N; Y[1] = N + 1; 
	for(int i = 2; i <= N; i++){
		ll t = (i >= 3 ? Y[i-3] : 0) + (N-i+1);
		X[i] = (X[i-1] + t + (ll)(N-1) * (N-1)) % MM;
		Y[i] = (Y[i-1] + X[i]) % MM;
	}
	printf("%lld\n", X[N]);
}
