Rightmost Nonzero Digit of Factorial

Given a positive integer \(N\) (\(1 \le N \le 5 \times 10^7\)), compute the rightmost nonzero digit of \(N!\).

The factorial of \(N\) is defined as:

[ N! = 1 \times 2 \times 3 \times \cdots \times 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 nonzero digit of \(12!\) is 6.

Note: For instance, \(10{,}000{,}000!\) ends with 2,499,999 trailing zeros, so direct computation of the full factorial is impractical.

Your task is to write a program to calculate the rightmost nonzero digit of \(N!\).

inputFormat

The input consists of a single line containing a positive integer \(N\) (\(1 \le N \le 5 \times 10^7\)).

outputFormat

Output a single digit, which is the rightmost nonzero digit of \(N!\).

sample

5

2