题目描述

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

输入格式

输入n 。

输出格式

如题述，之和。

样例

输入

10

输出

37913

数据规模与约定

对于所有数据，1≤n≤999999 。