Trên bảng \(A\) gồm \(n\) hàng và \(n\) cột, các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Tiến hành điền các số theo quy tắc: Trên hàng \(i\) (\(1 \le i \le n\)) lần lượt điền các số chẵn bắt đầu từ \(2 \cdot i\). Cụ thể, các số \(2 \cdot i, 2 \cdot (i + 1), \dots, 2 \cdot (i + n - 1)\) được điền trên hàng \(i\).

Ví dụ, với \(n = 4\) ta có bảng số sau:

Yêu cầu: Cho \(n\), hãy tính tổng các số điền trong bảng.

Input

• Gồm một số nguyên dương \(n\) (\(n \le 10^9\)).

Output

• Gồm một số là tổng tính được chia dư cho \(10^9 + 7\).

Example

2

16

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n \le 10^2\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^6\).
• Subtask \(3\) (\(10\%\) số điểm): Không có ràng buộc nào thêm.