N N N 的阶乘（记作 N ! N! N!）是指从 1 1 1 到 N N N（包括 1 1 1 和 N N N）的所有整数的乘积。

阶乘运算的结果往往都非常的大。

现在，给定数字 N N N，请你求出 N ! N! N! 的最右边的非零数字是多少。

例如 5 ! = 1 × 2 × 3 × 4 × 5 = 120 5!=1×2×3×4×5=120 5!=1×2×3×4×5=120，所以 5 ! 5! 5! 的最右边的非零数字是 2 2 2。

输入格式
共一行，包含一个整数 N N N。

输出格式
输出一个整数，表示 N ! N! N! 的最右边的非零数字。

数据范围
1 ≤ N ≤ 1000 1≤N≤1000 1≤N≤1000
输入样例：

7

输出样例：

4

解法一：
120 ! 120! 120!的阶乘远远超出了 l o n g l o n g long long longlong的范围，不过我们只需要获取最后的非零元素，所以只需要做一下控制，使其控制在 1 e 9 1e9 1e9的范围内。

控制的方法有两种：

1. 去掉末尾的 0 0 0，即不断除 10 10 10，因为最后的非零位之后的 0 0 0对答案毫无影响。
2. 对阶乘的结果膜 1 e 9 1e9 1e9，由于第一步操作，后续不可能出现连续的 9 9 9个 0 0 0，所以我们可以对其进行取模，控制范围

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;
int cnt2,cnt5;

int main() {
    ll res = 1;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        int tmp = i;
        while (tmp % 2 == 0) {
            cnt2++;
            tmp /= 2;
        }
        while (tmp % 5 == 0) {
            cnt5++;
            tmp /= 5;
        }
        res = res * tmp % 10;
    }
    for (int i = 1; i <= cnt2 - cnt5; i++) res = res * 2 % 10;
    printf("%lld\n", res);
    return 0;
}

解法二：
我们进行观察，因为 0 0 0只可能由 2 2 2的倍数和 5 5 5的倍数相乘得到，所以在进行乘法的过程中，我们将 2 2 2和 5 5 5的倍数给清理掉，这样就保证了不会出现0，然后我们控制其范围，每次相乘取其个位，因为个位肯定是非零元素，十位以后的数字完全没有必要保留下来，最后，我们将多处理的 2 2 2或者 5 5 5重新乘回去再取余即可。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;

int main() {
    ll res = 1;
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++) {
        res = res * i;
        while (res % 10 == 0) res /= 10;
        res %= 1000000000;
    }
    printf("%lld\n", res % 10);
    return 0;
}