Факторіали
Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.
Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа N!, що записують безпосередньо перед нулями наприкінці запису числа N!. Наприклад:
при N = 7 кодом буде 504, бо 7! = 5040;
при N = 17 кодом буде 096, бо 17! = 355687428096000.
За даним натуральним числом N знайти три послідовні цифри числа N!, що записують безпосередньо перед нулями наприкінці запису числа N!.
Вхідні дані
Вхідний файл містить єдине ціле число N. 7 ≤ N ≤ 1000000000.
Вихідні дані
Вихідний файл має містити рівно три цифри — шуканий код.