문제 130
정수 분할 수
음이 아닌 정수 $n$을 양의 정수들의 합으로 나타내는 방법의 수를 $p(n)$이라고 하자. 순서만 다른 표현은 같은 방법으로 세며 $p(0)=1$로 정의한다.
음이 아닌 정수 $N$과 양의 정수 $M$이 주어진다. $p(0), p(1), \cdots, p(N)$을 각각 $M$으로 나눈 나머지를 구해 보자.
입력
첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1\le T\le1\,000)$
두 번째 줄부터 $T$개의 줄에 걸쳐 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(0\le N\le100\,000; 1\le M\le2^{31}-1)$ $M$은 소수일 필요가 없다.
모든 테스트 케이스에 대한 $N$의 합은 $100\,000$ 이하이다.
출력
각 테스트 케이스에 대해 $p(0), p(1), \cdots, p(N)$을 $M$으로 나눈 나머지를 공백으로 구분하여 한 줄에 출력한다.
예제 입력 1
4 0 1 0 2147483647 10 1000 10 4
예제 출력 1
0 1 1 1 2 3 5 7 11 15 22 30 42 1 1 2 3 1 3 3 3 2 2 2