Cho dãy số 2, 4, 11, 13, 20, 22,... . Tính tổng các số trong dãy số có giá trị bé hơn hoặc bằng \(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 1000.

Input

• Gồm một số tự nhiên \(N\) duy nhất
• Giới hạn: \(1 \leq N \leq 10^9\)

Output

• Gồm một dòng duy nhất là kết quả bài toán

Example

4

6