Vào năm 2027, Chiến dịch Giám sát Không gian số Quốc gia triển khai Vệ tinh "VNASAT-2027" để thu thập dữ liệu định vị quỹ đạo. Để bảo mật đường truyền thông tin về Trung tâm Điều hành Mặt đất, hệ thống nén dữ liệu dưới dạng một khối mã hóa ~N!~ (~N~ giai thừa) cực lớn.

Tuy nhiên, do ảnh hưởng của nhiễu bức xạ không gian, các bit dữ liệu tương ứng với các chữ số ~0~ liên tiếp tính từ cuối của giá trị ~N!~ bị suy hao tần số và biến dạng hoàn toàn. Để khôi phục chuẩn xác cấu trúc khung truyền tín hiệu, hệ thống giải mã tự động cần xác định chính xác số lượng chữ số ~0~ bị mất này.

Biết rằng tham số nén ~N~ có giá trị lên tới ~10^{18}~. Nếu tính trực tiếp giá trị ~N!~ thì bộ nhớ của vệ tinh sẽ bị tràn ngay lập tức. Do dung lượng của thanh ghi giải mã năm 2027 có giới hạn, Trung tâm Điều hành yêu cầu chương trình phải xuất ra kết quả là số lượng chữ số ~0~ liên tiếp tính từ cuối của ~N!~, được chia lấy dư cho ~10^9 + 7~ ~(1000000007)~.

Yêu cầu: Hãy viết chương trình xử lý nhanh tín hiệu không gian số này giúp Trung tâm Điều hành trước khi Vệ tinh di chuyển sang vùng khuất sóng.

Input

• Một dòng duy nhất chứa một số nguyên dương ~N~ ~(1 \le N \le 10^{18})~.

Output

• In ra một số nguyên duy nhất là số lượng chữ số ~0~ liên tiếp tính từ cuối của ~N!~ sau khi chia lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

10

Sample Output 1

2

Notes

~10! = 3628800~, có ~2~ chữ số ~0~ liên tiếp ở cuối.