EIU ACM Preparation

Start

2018-05-31 09:30 UTC

EIU ACM Preparation

End

2018-06-01 15:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -445 days 6:59:16

Time elapsed

30:00:00

Time remaining

0:00:00

Problem C
Three Digits

Per is obsessed with factorials. He likes to calculate them, estimate them, read about them, draw them, dream about them and fight about them. He even has the value of $12!=479\, 001\, 600$ tattooed on his back.

He noticed a long time ago that factorials have many trailing zeroes and also wrote a program to calculate the number of trailing zeroes. For example $12!$ ends with 600, so it has 2 trailing zeroes. Now he wants to make one step further, look at the 3 digits right before the trailing zeroes. In the case of $12!$, the last 3 digits before the trailing zeroes are $016$.

Task

Given an integer $n$, find the last 3 digits before the trailing zeroes in $n!$. If there are fewer then 3 such digits, find all of them.

Input

The input contains one line with one integer $n$ ($1\leq n\leq 10\, 000\, 000$).

Output

Output one line with the 3 digits before trailing zeroes of $n!$. If there are fewer than 3 such digits, output all of them.

Sample Input 1 Sample Output 1
5
12
Sample Input 2 Sample Output 2
14
912