给定一个正整数 nn，请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位（不含前导 00）。x!x! 表示 xx 的阶乘，即 1*2*3*\ldots*x1∗2∗3∗…∗x。 【输入格式】 给定一个正整数 nn，请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位（不含前导 00）。x!x! 表示 xx 的阶乘，即 1*2*3*\ldots*x1∗2∗3∗…∗x。 【输入格式】

输入包含一个正整数 n（1≤n≤1091≤n≤109）。 【输出格式】 输出一个整数，表示 S 的末 66 位。 【输入样例】 5 【输出样例】 874166702539019172 我们可以先算出每个数的末6位，然后再累加。由于一个数的末6位只与它的末3位有关，因此我们可以先预处理出1!到n!的末3位，然后再计算末6位。具体地，我们可以将每个数拆成一个后缀和一个前缀，其中前缀是一个6的倍数，后缀的位数不超过3。那么每个数对应的后缀就是其末3位的阶乘，而前缀只有4种情况，即0,6,12,18。我们可以将1!到n!按照前缀分类，然后对于每种前缀单独计算后缀的乘积，最后再将所有结果累加即可得到答案。时间复杂度为O(logn)。