Một dãy con lắc được tạo ra từ một số nguyên dương \(N\) theo quy luật:

• Dãy đầu tiên: từ \(1\) đến \(N\)
• Sau đó: từ \(N-1\) về \(2\)
• Tiếp theo: từ \(3\) đến \(N-2\)
• Tiếp tục như vậy cho đến khi không còn số nào để tạo thành dãy mới
  ...

Ví dụ: dãy số con lắc khi \(N=6\): \(1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4\).

Yêu cầu

• Tính tổng các phần tử xuất hiện trong dãy con lắc trên, sau đó lấy phần dư chia cho \(100\).

Input

• Một dòng duy nhất chứa một số nguyên \(N\) (\(1 \le N \le 10^8\)).

Output

• Một dòng duy nhất là phần dư khi tổng chia cho 100.

Example

6

42

Scoring

• Subtask \(1\) (\(30\) điểm): \(N \le 100\).
• Subtask \(2\) (\(30\) điểm): \(N \le 10^4\).
• Subtask \(3\) (\(40\) điểm): \(N \le 10^8\).