Counting Trailing Zeros in the Product of Factorials

Given a positive integer n, compute the number of trailing zeros in the product

\(P = 1! \times 2! \times 3! \times \cdots \times n!\)

The trailing zeros of P are determined by the number of factors of 10 in P. Since 10 = 2 \(\times\) 5 and factors of 2 are more abundant than factors of 5, the number of trailing zeros is equal to the total number of factors of 5 in P. Note that for each factorial i!, the exponent of 5 (denoted as \(v_5(i!)\)) is given by:

\(v_5(i!) = \left\lfloor \frac{i}{5} \right\rfloor + \left\lfloor \frac{i}{25} \right\rfloor + \left\lfloor \frac{i}{125} \right\rfloor + \cdots\)

Your task is to compute the sum \(v_5(1!) + v_5(2!) + \cdots + v_5(n!)\), which is the number of trailing zeros in P.

inputFormat

The input consists of a single integer n (n ≥ 1).

outputFormat

Output a single integer representing the number of trailing zeros in the product P = 1! \times 2! \times ... \times n!.

sample

4

0