Một dãy số gồm n số nguyên dương ~a_1, a_2,..., a_n~ được gọi là dãy số đặc biệt nếu thỏa mãn đồng thời các điều kiện sau:

1. Giá trị của các số hạng không vượt quá ~n~.

2. Tồn tại số hạng ~a_i~ sao cho ~a_i < a_{i - 1}~ với ~1 < i ≤ n~.

3. Tồn tại số hạng ~a_j~ sao cho ~a_j > a_{j - 1}~ với ~1 < j ≤ n~.

Yêu cầu: Cho một số nguyên dương n, hãy lập trình đếm số lượng dãy số đặc biệt có n số.

Input

• Một dòng duy nhất ghi một số nguyên dương ~n~.

Output

• Một số nguyên duy nhất là kết quả tìm được khi chia lấy dư cho ~1000000007~.

Scoring

Sample Input 1

3

Sample Output 1

10

Note

Giải thích ví dụ:

Các dãy đặc biệt là: (1,2,1), (1,3,1), (1,3,2), (2,3,1), (2,1,3), (2,1,2), (2,3,2), (3,1,2), (3,1,3), (3,2,3).