6. 阶乘的和

【题目描述】

小 C 刚学习了阶乘的定义：$n!=1 \times 2 \times 3 \times \cdots \times n$。他发现这个数字增长极快，于是想算算 $1 \sim n$的所有阶乘之和，也就是 $S=\displaystyle\sum_{i=1}^n i!$。

这个和太大了，所以请你帮他求出 $S \bmod 10000$ 的值。

【输入格式】

第一行输入一个正整数 $n$（$1 \le n \le 10^9$）表示求和的项数。

【输出格式】

输出一行一个非负整数，表示 $S \bmod 10000$ 的值。

【输入样例 1】

3

【输出样例 1】

9

【输入样例 2】

10

【输出样例 2】

7913

【输入样例 3】

20

【输出样例 3】

313

【样例说明】

$n=3$ 时，$S=\displaystyle\sum_{i=1}^3 i!=1!+2!+3!=1+2+6=9$，$S \bmod 10000=9$。

$n=10$ 时，$S=\displaystyle\sum_{i=1}^{10} i! = 1+2+6+24+120+720+5040+40320+362880+3628800 = 4037913$，$S \bmod 10000 = 7913$。

【来源】

ICPC 2026 河南省赛。