20231115 - 阶乘之和

通过次数

2

提交次数

3

Time Limit : 1 秒
Memory Limit : 128 MB

输入n,计算S=1!+2!+3!+…+n!的末6位(不含前导0)。n≤10⁶, n!表示前n个正整数之积。

Input

输入n。

Output

如题述,之和。

Examples

Input

10

Output

37913

Source

信奥赛