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, tức là ~S = 1! + 2! + \ldots + n!~. Hãy lập trình tính số dư của ~S~ trong phép chia cho ~20240131~.

Dữ liệu

Một số nguyên dương ~n~.

Kết quả

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

Ví dụ

FACTORIAL.INP

4

FACTORIAL.OUT

33

Giải thích: ~S = 1! + 2! + 3! + 4! = 33~.

Giới hạn

• Subtask 1: ~n \le 18~.
• Subtask 2: ~n \le 10^5~.
• Subtask 3: ~n \le 10^{18}~.