eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Факторіали

Факторіали

Лимит времени 1 секунда
Лимит использования памяти 32 MiB

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа N!, що записують безпосередньо перед нулями наприкінці запису числа N!. Наприклад:

  • при N = 7 кодом буде 504, бо 7! = 5040;

  • при N = 17 кодом буде 096, бо 17! = 355687428096000.

За даним натуральним числом N знайти три послідовні цифри числа N!, що записують безпосередньо перед нулями наприкінці запису числа N!.

Входные данные

Вхідний файл містить єдине ціле число N. 7N1000000000.

Выходные данные

Вихідний файл має містити рівно три цифри — шуканий код.

Пример

Входные данные #1
17
Выходные данные #1
096