Факториалы

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

Грабители уверены, что код состоит из трех последовательных цифр числа N!, которые стоят непосредственно перед нулями в конце записи числа N!. Например:

• для N = 7 код — 504, так как 7! = 5040;

• для N = 17 код — 096, так как 17! = 355687428096000.

По заданному натуральному числу N необходимо найти три последовательные цифры числа N!, которые стоят непосредственно перед нулями в конце его записи.