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>
#define IL inline
#define _ 1000005
#define ll long long
using namespace std ;

int n , f[_] , s[_] , p[_] , Ans ;
#define mod 1000000007

int main() {
	cin >> n ; 
	for(int i = 1; i <= n; i ++) {
		f[i] = ((i >= 3) ? p[i - 3] : 0) + 1 ;
		s[i] = (s[i - 1] + f[i]) % mod ; p[i] = (p[i - 1] + s[i]) % mod ; 
	}
	Ans = 0 ;
	for(int i = 1; i < n; i ++) Ans = (Ans + 1ll * f[i] * (n - 1) % mod * n % mod) % mod ;
	cout << (Ans + 1 + 1ll * f[n] * (n - 1) % mod) % mod  << endl ;
	return 0 ; 
}
