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 long long int MOD=1e9+7;
int main(){
  long long int n;
  cin>>n;
  vector<long long int> dp(n,0); //dp[i]=(rest i+1 char);
  dp[0]=n;
  long long int sum=dp[0];
  if(n!=1) dp[1]=n*n,sum+=dp[1];
  for(int i=2;i<n;i++){
    dp[i]=sum-(i-2>=0 ? dp[i-2] : 0)+((n-1)*(n-1))%MOD+n-i+1;
    dp[i]%=MOD;
    sum+=dp[i];
    sum%=MOD;
  }
  dp[n-1]=(dp[n-1]+MOD)%MOD;
  cout<<dp[n-1]<<endl;
  return 0;
}
