Divisibility of binomial coefficients#648

Divisibility of binomial coefficients

2 seconds
64 megabytes
Easy

Let C^i_n be the binomial coefficient, where 0 \leq i \leq n and , are integers. You are given a positive integer and a prime number . Let be the largest non-negative integer such that p^k \leq n. For each j \geq 0, let a_j be the number of integers i \in \{0, 1, \ldots, n\} such that C^i_n is divisible by p^j, but not divisible by p^{j+1}. It is easy to verify that a_j = 0 for j > k. Therefore, you are required to find the numbers a_0, a_1, \ldots, a_k.

Input

The only line contains a positive integer (n \leq 10^{18}) and a prime number (p < 10^{18}).

Output

Output in a single line the numbers a_0, a_1, \ldots, a_k separated by spaces.

Examples

Example 1

Loading
Loading