【题目描述】

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

【输入】

输入$n$。

【输出】

如题述，之和。

【输入样例】

10

【输出样例】

37913

【提示】

【数据范围】 对于所有数据，$1\le n \le 999999$。

题目来源：信息学奥赛一本通 2033；数据整理来源：ROJ 5035。