Quang là một học sinh yêu thích môn Toán học. Hôm nay, Quang đang nghiên cứu về phép toán giai thừa, một phép toán có nhiều ứng dụng trong các ngành khác nhau. Quang đã tìm hiểu và biết rằng giai thừa của một số nguyên dương ~n~ là tích của các số nguyên từ ~1~ đến ~n~.

Cho một số nguyên dương ~n~, gọi ~S~ là tổng giai thừa của ~n~ số nguyên dương đầu tiên: ~S = 1! + 2! + 3! + \dots + n!~.

Yêu cầu: Hãy lập trình giúp Quang tính số dư của ~S~ khi chia cho ~20241101~.

Input

• Dòng duy nhất chứa số nguyên dương ~n~.

Output

• Ghi ra một số nguyên duy nhất là phần dư của ~S~ khi chia cho ~20241101~.

Sample Input 1

3

Sample Output 1

9