题目描述

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

输入

输入$n$。

输出

如题述，之和。

输入样例

10

输出样例

37913

提示

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

评测数据说明

本题使用依题意重新构造并经独立双实现核对的训练数据，共9个测试点，非原站或官方原始数据。每题总分100分。