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
n = input()

"""
from itertools import *

ans = 0

for a in product(range(1,n+1), repeat=n):
    a = a + (a[-1],)*n
    ok = True
    for i in range(n):
        if len(set(a[i+1:i+a[i]+1]))!=1:
            ok = False
    if ok:
        print a
        ans += 1
print ans
"""

M = 10**9+7
T = [0]*n
X = n-1
for i in range(n)[::-1]:
    if i==n-1:
        T[i] = n
    elif i==n-2:
        T[i] = n*n
    else:
        #for a in range(2,n+1):
        #    t = i+1+a
        #    T[i] += T[t] if t<n else 1
        X -= 1
        X += T[i+3] if i+3<n else 1
        X %= M
        T[i] += T[i+1] + (n-1)*(n-1) + X
    T[i] %= M
print T[0]
