题目描述

输入 $n$，计算 $S＝1！＋2！＋3！＋ \ldots ＋n！$ 的末 $6$ 位（不含前导 0）。$n！$ 表示前 $n$ 个正整数之积。

提示：$n！=1*2*3*4*...*n$

输入格式

一个整数，表示$n$($n \leq 10^{6}$)。

输出格式

输出 $S$。

样例

样例输入

10

样例输出

37913

数据范围与提示

提示： 输出的答案要 mod 1000000！！！

• 考虑程序是否可以优化
• 考虑程序是否可以进一步优化， 是否可以进一步优化你的程序呢。