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 <cstdio>
typedef long long ll;

const int N = 1001000, p = 1e9+7;
inline int qm(const int x) {return x < p ? x : x - p;}
int n, a, b, c, d;

int main() {
	scanf("%d",&n);
	if(n == 1) return puts("1"), 0;
	if(n == 2) return puts("4"), 0;
	c = n, b = (ll)n * n%p;
	int sm = 0;
	for(int i=n-2;i;--i) {
		sm = qm(sm + d);
		a = (sm + b + (ll)(n-1)*(n-1) + i+1)%p;
		d = c, c = b, b = a;
	}
	printf("%d\n", b);
	return 0;
}