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;

typedef long long ll;

ll dyn[1000100], ps[1000100];
ll MOD = 1000000007, n;

int main() {
    int i;
    dyn[0] = ps[0] = 1;
    scanf("%lld",&n);
    for (i=1;i<=n;i++) {
        dyn[i] = (dyn[i-1] + ((i>=3)?ps[i-3]:0))%MOD;
        ps[i] = (ps[i-1]+dyn[i])%MOD;
    }
    ll sum = 0;
    for (i=0;i<n-1;i++) {
        sum += (dyn[i]*(((n-1)*(n-1))%MOD+i+1))%MOD;
        sum %= MOD;
    }
    sum += (dyn[n-1]*(n-1))%MOD;
    sum += dyn[n];
    printf("%lld\n",sum%MOD);

    return 0;
}
