Count the trailing zeroes in the decimal representation of \(N!\).

Input

One line containing \(N\).

The input satisfies:

• \(1 \le N \le 10^18\)

Output

Print the count modulo \(1,000,000,007\).

Example

Input

1

Output

0