Description

Perhaps you already know what a factorial is; the factorial of $N$ is the product from $1$ to $N$, for example:

$$12!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times 12=479{,}001{,}600$$

The rightmost non-zero digit of the factorial of $12$ is $6$.

Write a program to compute the value of the rightmost non-zero digit of the factorial of $N\ (1\le N\le5\times 10^7)$.

Note: There are $2499999$ trailing zeros in $10{,}000{,}000!$.

Input Format

A single line containing a positive integer $N$.

Output Format

A single integer, the value of the rightmost non-zero digit.

12

6

Hint

USACO Training Section 3.2.

Translated by ChatGPT 5