题目描述

求 $1!+2!+\cdots+n!$ 的末六位，不保留前导零。

输入格式

一行一个整数 $n$。

输出格式

输出阶乘之和除以1000000的余数。

样例

10

37913

数据范围

$1\le n\le10^6$。