题目描述

也许你早就知道阶乘的含义，$N$ 阶乘是由 $1$ 到 $N$ 相乘而产生，如：

$12$ 的阶乘最右边的非零位为 $6$。

写一个程序，计算 $N\ (1\le N\le5\times 10^7)$ 阶乘的最右边的非零位的值。

注意：$10{,}000{,}000!$ 的末尾有 $2499999$ 个零。

输入格式

仅一行包含一个正整数 $N$。

输出格式

一个整数，表示最右边的非零位的值。

12

6

提示

USACO Training Section 3.2