C. The revenge of GrandPaPà
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
De mă voi scula, pre mulţi am să popesc şi eu…
— Costache Negruzzi, Alexandru Lăpuşneanu

The Romanian word "popeală" has its origins in a Romanian historical novella, "Alexandru Lăpușneanul", where the eponymous Prince of Moldavia uses a variation of the term to describe his upcoming revenge on his usurpers. The term was recently revived, somewhat surprisingly, in the Romanian programming contest scene. It's used to describe any situation in which the scientific committee makes life harder for the contestants in an unorthodox and (usually) involuntary way: very strict time limits, invalid test cases, wrong statements,wrong statements, stealing keyboards and other such mechanisms. This task is about such a "popeală". Source : CEOI 2016 , Romania

GrandPaPà is very upset that nobody liked his problems in the past InfoLeague™ contest. He wants to take revenge for that **insert Pablo Escobar**. He gives you nicely throws you number N. He then asks you nicely orders you to find the number of permutations of length N such that the maximum size of a subsequence ( contiguous indices ) that only has consecutive values is exactly equal to K. For example , [1, 2, 3, 4] would satisfy K = 4 ( [1, 4] is the best subsequence ) while [3, 1, 2, 4] will satisfy K = 2 ( [2, 3] is the best subsequence ). If you can solve this task , GrandPaPà will be happy once again. Else he will **redacted**.

Input

The input consists of two integers N (1 ≤ N ≤ 2000) — the length of the permutations, and MOD (1 ≤ MOD ≤ 109) — the modulo used to compute the answer.

Output

The output consists of N integers , the number of permutations which hold the propriety for every K in the set {1,2,3...,N}. This means you need to solve the problem for every possible K and print the answers. Since the answers may be very large, print them modulo MOD.

Scoring
  • For all test data , 1 ≤ N ≤ 2000 , 1 ≤ MOD ≤ 109.
  • For 10 points , 1 ≤ N ≤ 11.
  • For another 50 points , 11 < N ≤ 500.
  • For the remaining 40 points , there are no further restrictions.
  • MOD may not be a prime number !!!
Example
Input
3 666013
Output
3 2 1
Note

Let's look at all the permutations of length 3.

  • [1,2,3] => K = 3 ( sequence [1,3] is consisting of consecutive values and has maximal length 3 )
  • [1,3,2] => K = 1 ( sequences [1,1],[2,2],[3,3] are consisting of consecutive values and have maximal length 1)
  • [2,1,3] => K = 1 ( sequences [1,1],[2,2],[3,3] are consecutive and have maximal length 1)
  • [2,3,1] => k = 2 ( sequence [1,2] is consisting of consecutive values and has maximal length 2 )
  • [3,1,2] => k = 2 ( sequence [2,3] is consisting of consecutive values and has maximal length 2 )
  • [3,2,1] => k = 1 ( sequences [1,1],[2,2],[3,3] are consecutive and have maximal length 1)

Thus , we need to print [3 mod 666013 , 2 mod 666013 , 1 mod 666013] = [3,2,1].