Problems
Факторіали
Факторіали
Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.
Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа \textbf{N!}, що записують безпосередньо перед нулями наприкінці запису числа \textbf{N!}. Наприклад:
\begin{itemize}
\item при \textbf{N = 7} кодом буде \textbf{504}, бо \textbf{7! = 5040};
\item при \textbf{N = 17} кодом буде \textbf{096}, бо \textbf{17! = 355687428096000}.
\end{itemize}
За даним натуральним числом \textbf{N} знайти три послідовні цифри числа \textbf{N!}, що записують безпосередньо перед нулями наприкінці запису числа \textbf{N!}.
\InputFile
Вхідний файл містить єдине ціле число \textbf{N}. \textbf{7} ≤ \textbf{N} ≤ \textbf{1000000000}.
\OutputFile
Вихідний файл має містити рівно три цифри --- шуканий код.
Input example #1
17
Output example #1
096