Counting Phenomenal Arrays#13032

Counting Phenomenal Arrays

2 seconds
256 megabytes
Very hard

Let's call an array [a_1, a_2, \ldots, a_k] of positive integers phenomenal, if the product of its elements is equal to the sum of its elements (i.e. if a_1 a_2 \ldots a_k = a_1 + a_2 + \ldots + a_k) .

For example, the array is phenomenal, because 2\cdot 2 = 2+2 = 4, and [3, 1, 2] is phenomenal, because 3\cdot 1 \cdot 2 = 3 + 1 + 2 = 6, but the array is not phenomenal, as 2\cdot 3 \neq 2+3.

Let denote the number of phenomenal arrays of size . It can be shown that for any fixed i \ge 2 there is only a finite number of phenomenal arrays of size .

You are given an integer . Find f(2), f(3), \ldots, f(n). As these numbers can be very big, output them modulo , where is a given prime number.

Input

The only line of the input contains two integers (2 \le n \le 2\cdot 10^5, 10^8 \le P \le 10^9, is prime).

Output

Output n-1 integers — the values f(2), f(3), \ldots, f(n) modulo .

Examples

Example 1

Loading
Loading