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