Ban đầu có dãy số tự nhiên lẻ vô tận: \(1, 3, 5, 7, 9, 11, \dots\)

Lấy tích hai số liên tiếp của dãy số trên được dãy số mới: \(3, 15, 35, 63, 99, \dots\)

Hãy tính tổng của \(N\) số hạng đầu tiên của dãy số mới.

Input

• Gồm một số tự nhiên \(N\) (\(1 \le N \le 10^9\)).

Output

• Một số tự nhiên là kết quả của bài toán. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho \(2026\).

Example

3

53

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 10^2\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 10^4\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.