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 <iostream>
#include <vector>

int main() {
    long long n, par = 0;
    constexpr auto mod = 1000000007;
    std::cin >> n;
    std::vector<long long> v(n + 1);

    v[0] = 1;
    v[1] = n;
    v[2] = n * n;
    for (auto i = 3ll; i <= n; i++) {
        par = (par + v[i - 3]) % mod;
        v[i] = ((n - 1) * (n - 1) + v[i - 1] + n - i + 1 + par) % mod;
    }
    std::cout << v[n] << std::endl;

    return 0;
}