Cho 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. Hãy lập trình tính số dư của \(S\) trong phép chia cho 20240131.

Dữ liệu vào

• Một số nguyên dương \(n\).

Dữ liệu ra

• Một số nguyên duy nhất là số dư của \(S\) trong phép chia cho 20240131.

Ràng buộc:

• Subtask \(1\): \(n \le 18\)
• Subtask \(2\): \(n \le 10^5\)
• Subtask \(3\): \(n \le 10^{18}\)

Input 1

4

Output 1

33

Giải thích:

• S = 1! + 2! + 3! + 4! = 33