Big Factorials

Given an integer N, print the trailing 4 digits of $N!$ (N factorial).

$N! = N \times (N-1) \times (N-2) \times ... \times 1$

Here are some examples of $N!$ and their last 4 digits.

Input

The input will contain an integer $N$ ($0 < N < 1000$).

Output

Print the last 4 digits of $N!$. In case $N!$ has less than 4 digits, do not print any leading zeros.

Samples

4

24

10

8800