$O(n)$

保留末尾9位数字只需要对结果取余 $10^9$，设 $mod = 10^9$.

$$ans = (1!+2!+...+(N-1)!+N!) \% mod$$ $$ans = (1! \% mod + 2! \% mod +...+(N-1)! \% mod +N! \% mod) $$

当因子包括 $10^9$ 时取余结果为 $0$. 对阶乘来说每一项又是前一项的倍数，这意味着从某一项开始，后面的结果全为 $0$ .

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 2e5 + 10, mod = 1e9;


int main()
{
    int n;
    cin >> n;
    LL ans = 0, t = 1;
    for(int i = 1; i <= n; i ++)
    {
        t = (t * i) % mod;
        if(t == 0) break;
        ans = (ans + t) % mod;
    }
    cout << ans << endl;
}