Cho dãy số có quy luật như sau:

\(1, 4, 5, 8, 9, 12, 13, 16, 17, 20, \ldots\)

Dãy số trên gồm các số tự nhiên khi chia cho \(4\) có số dư là \(0\) hoặc \(1\), được viết theo thứ tự tăng dần.

Yêu cầu

Cho số tự nhiên \(K\), hãy tính tổng \(K\) số đầu tiên của dãy. Vì kết quả có thể rất lớn, chỉ cần in ra phần dư của kết quả khi chia cho \(2026\).

Input

• Gồm một dòng duy nhất chứa số tự nhiên \(K\) (\(1 \le K \le 10^{12}\)).

Output

• In ra một số tự nhiên duy nhất là phần dư của tổng \(K\) số đầu tiên của dãy khi chia cho \(2026\).

Example

5

27

10

110

Scoring

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