Cho một dãy số có công thức sau:

• \(A_1 = 1\)
• \(A_2 = 1\)
• \(A_3 = 1\)
• \(...\)
• \(A_i = 3 \times A_{i-1} - 2 \times A_{i-2} + i^2 - 1\)

Dữ liệu vào

• Một dòng gồm số nguyên \(n\).

Dữ liệu ra

• In ra số thứ \(n\) của dãy số modulo \(10^9+7\)

Điều kiện

• \(1 \le n \le 10^{9}\).

Input 1

4

Output 1

16