Cho dãy số ~2,4,11,13,20,22, ...~ Tính tổng các số trong dãy có giá trị bé hơn hoặc bằng ~n~. Vì kết quả rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho ~1000~.

Input

• Một dòng chứa một số nguyên ~n~ ~(0 \le n \le 10^9)~.

Output

• In ra một số nguyên duy nhất là kết quả bài toán.

Scoring

• Nếu chương trình chạy đúng những trường hợp ~0 \le n \le 10^5~, thí sinh sẽ được ~60~ điểm.
• Nếu chương trình chạy đúng toàn bộ các trường hợp ~0 \le n \le 10^9~, thí sinh sẽ được ~100~ điểm.

Sample Input

30

Sample Output

101