집합 S는 1부터 n까지의 자연수만을 원소로 갖는다.  S의 부분집합 중, 원소의 합을 p로 나눈 나머지가 k인 것들을 k-부분집합이라 부르자.

 n과 p가 주어졌을 때, 가능한 모든 k에 대해 k-부분집합의 개수를 출력하시오.

(* 공집합은 원소의 합이 0인 부분집합이라 생각한다.)

첫 줄에 자연수 n과 소수 p가 공백을 기준으로 주어진다.

( 1 ≤ n ≤ 2⁶³ - 1, 2 ≤ p ≤ 5000)

예시 설명

0-부분집합 : { }, {3}, {1, 2}, {1, 2, 3}

1-부분집합 : {1}, {1, 3}

2-부분집합 : {2}, {2, 3}