Description

求 s=1!+2!+...+n!的末 6 位数，n 不大于 10000000。

Format

Input

输入n。

Output

输出末6位数。

Samples

10

37913

Hint