프로그램 명: fac
제한시간: 1 초

N!의 끝에서 연속하는 0의 개수를 출력하는문제이다. 단, N! = N * (N-1) * (N-2) . . . * 3 * 2 * 1

예를들어 10! = 3628800 임으로 끝에서 연속하는0의 개수는 2이다.

입력

N이 주어진다. ( 1 <= N <= 1,000,000,000,000,000,000 )

출력

끝에서 연속하는 0의 개수를 출력한다. 단, 숫자가 너무커질수 있으므로 500,000,000,000,000,007로 나눈 나머지 값을 출력한다.

입출력 예


입력 

1

출력

0

입력

10

출력

2


입력

100

출력

24

입력

1422534662

출력

355633660
출처:makesource

[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]