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
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

def get(i):
    #if i==-n: return 0
    if i <= 0: return 1
    else: return a[i]


n, = map(int,readline().split())

MOD = 10**9+7

a = [1,n,n*n]
for i in range(3,n+1):
    res = -get(i-n-2) + get(i-3) - get(i-2) + 2*get(i-1)
    a.append(res%MOD)

#print(a)
print(a[-1])











