Testing problem, khuyến khích không nên làm

Cho $1$ số nguyên dương $n$. Tính kết quả $n!\ mod\ 10^9$, biết $n!=1.2.3...(n-1)n$ và $mod$ là phép chia lấy dư

Input(Bàn phím):

• Gồm $1$ số nguyên dương $n(1\le n\le 10^{18})$.

Output(Màn hình):

• In ra kết quả của $n!\ mod\ 10^9$.

Standard input

6

Standard output

720

Subtask:

• Có $50$% số test có $1\le n\le 50$
• Có $25$% số test có $1\le n\le 10^9$
• Có $25$% số test có $1\le n\le 10^{18}$