Cho dãy số vô hạn có quy luật như sau: \(3, 2, 1, 6, 5, 4, 9, 8, 7, \dots\)

Yêu cầu: Cho số nguyên dương \(K\), hãy tính tổng \(K\) số hạng đầu tiên của dãy số. Kết quả cần in ra là số dư khi chia tổng đó cho \(2026\).

Input

• Gồm một dòng chứa số nguyên dương \(K\) (\(1 \le K \le 10^9\)).

Output

• In ra một số nguyên duy nhất là kết quả của bài toán (lấy dư theo \(2026\)).

Scoring

• \(70\%\) số test tương ứng với \(K \le 10^3\).
• \(30\%\) số test còn lại không có ràng buộc bổ sung.

Example

5

17