Factorials

The President of the First National Bank, Major Thomas B. Kingman, transfers the contents of the safes, where the bank's clients store their valuables, every night. The robbers are aware of this routine, so they rented one of the safes in the bank, waiting for the president to mistakenly transfer something valuable into their safe. This strategy paid off when they got their hands on a box containing the major's own jewels! Now, the robbers have only a few hours to crack the three-digit combination lock, take the valuables, and return the box without anyone noticing the theft.

Knowing the major's fondness for large numbers, the robbers are convinced that the code is the three consecutive digits of the number (N!), located just before the trailing zeros at the end of (N!). For example:

- For (N = 7), the code is (504), because (7! = 5040). - For (N = 17), the code is (096), because (17! = 355687428096000).

Given a natural number (N), determine the three consecutive digits of (N!) that appear directly before the zeros at the end of (N!).

Input

The input file contains a single integer (N), where (7 $\le$ N $\le$ 1000000000).

Output

The output file must contain exactly three digits — the code you are looking for.

Examples