Description

N的阶乘写作N!表示小于等于N的所有正整数的乘积。阶乘会很快的变大，如13!就必须用32位整数类型来存储，70！即使用浮点数也存不下了。你的任务是找到阶乘最后面的非零位。举个例子,5!=1*2*3*4*5=120所以5!的最后面的非零位是2，7！=1*2*3*4*5*6*7=5040，所以最后面的非零位是4。

Input

共一行，一个整数不大于4,220的整数N。

Output

共一行，输出N!最后面的非零位。

Sample Input

7

Sample Output

4 这道题显然不能单纯直接使用循环来写，那样的话溢出是必然的。我是在每一次循环相乘结束之后，将后面的零清掉，然后取余。我一开始是取余100000000，但是其实只需要取余10000，保留后4位，用后面4位继续进行运算就可以了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6  7 using namespace std; 8  9 int main(void)10 {11     long long n,m;12     scanf("%lld",&n);13     m = 1;14     for(int i = 1; i <= n; i++)15     {16         m *= i;17         while(!(m % 10))18             m /= 10;19         m %= 10000;20     }21     while(!(m % 10))22             m /= 10;23     m %= 10;24     printf("%lld\n",m);25     return 0;26 }