eolymp
Задачи

Факторіали

Факторіали

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Лимит времени 1 секунда
Лимит использования памяти 32 MiB
Входные данные #1
17
Выходные данные #1
096