Mr. Santa asks all the great programmers of the world to solve a trivial problem. He gives them an integer m and asks for the number of positive integers n, such that the factorial of n ends with exactly m zeroes. Are you among those great programmers who can solve this problem?
Input
The only line of input contains an integer m (1 ≤ m ≤ 100 000) — the required number of trailing zeroes in factorial.
Output
First print k — the number of values of n such that the factorial of n ends with m zeroes. Then print these k integers in increasing order.
Examples
input
1
output
5
5 6 7 8 9
input
5
output
0
Note
The factorial of n is equal to the product of all integers from 1 to n inclusive, that is n! = 1·2·3·…·n.
In the first sample, 5! = 120, 6! = 720, 7! = 5040, 8! = 40320 and 9! = 362880.
Solution:
#include <bits/stdc++.h> using namespace std; inline int get(int n) { int z = 0; while (n > 0) { n /= 5; z += n; } return z; } int main() { int k; scanf("%d", &k); int low = 0, high = (int) 1e9; while (low < high) { int mid = (low + high) >> 1; int cnt = get(mid); if (cnt < k) { low = mid + 1; } else { high = mid; } } vector <int> res; while (get(low) == k) { res.push_back(low); low++; } int sz = res.size(); printf("%d\n", sz); for (int i = 0; i < sz; i++) { if (i > 0) { putchar(' '); } printf("%d", res[i]); } printf("\n"); return 0; }