我们定义n! = 1∗2∗...∗(n-1)∗n，s = 1∗1! + 2∗2! + ...+(n-1)∗(n-1)!，求 s mod n（mod为取余运算）。 输入格式: 输入在一行中给出一个正整数n，2≤n≤1018。 输出格式: 对于输入的n，输出s mod n的结果。

这个问题是一个经典的数学问题，通常称为“中国剩余定理”的简化版本。不过直接计算s mod n可能会因为数值过大导致溢出。我们可以采用一个叫做"累加器"的方法优化计算。

首先，注意到每个乘积(i * i!)都是i的阶乘除以n的余数的乘积。这是因为n能够整除i到n的所有数，所以i!对n取模等于1。这意味着我们实际上只需要找到1!到(n-1)!对n的余数，然后将它们相加再对n取模。

#include<stdio.h>

long long factorial_mod(long long n, long long p) {
    long long result = 1;
    for (long long i = 1; i <= n; i++) {
        result = (result * i) % p;
    }
    return result;
}

int main() {
    long long n;
    scanf("%lld", &n);
    
    long long modulos[64]; // 预估n不会超过1e18，取64位长度
    long long product = 1;

    // 计算每个i!对n的余数并保存至modulos数组
    for (int i = 0; i < 64 && product <= n; ++i, product *= 2) {
        modulos[i] = factorial_mod(product, n);
    }

    // 累加并取模
    long long ans = 0;
    for (int i = 0; i < 64; ++i) {
        if ((n >> i) & 1) { // 如果n的第i位是1，则加入当前余数
            ans += modulos[i];
            if (ans > n) {
                ans -= n;
            }
        }
    }
    printf("%lld\n", ans);

    return 0;
}

这个算法避免了直接计算大数阶乘和乘法操作，有效地解决了大数溢出的问题。