28689번 - 다포체수

문제

기하를 별로 좋아하지 않는 하늘이는 어디선가 도형수의 개념을 알아 왔다. 하늘이는 특히 삼각수와 사면체수라는 두 정수 수열에 대해 배웠다고 한다. 아래 두 그림은 각각 4번째 삼각수에 대응하는 크기 4의 삼각형(왼쪽)과 4번째 사면체수에 대응하는 크기 4의 사면체(오른쪽)이다.

하늘이는 $n$개의 평행한 평면에 크기 1ドル,ドル 2ドル,ドル $\cdots,ドル $n$의 삼각형을 하나씩 그려 합치면 $n$번째 사면체가 된다는 것을 깨달았다. 이를 일반화하여, $d$차원 상에서 모양이 하나 주어질 때, 크기 1ドル,ドル 2ドル,ドル $\cdots,ドル $n$의 해당 모양을 평행하게 쌓아 크기 $n$의 $(d+1)$차원 모양을 정의함으로써 모양을 확장할 수 있게 되었다!

여기서 하늘이는 $n$번째 모양의 점 개수가 어떤 다항식 수열 $p(n)$을 따르는 모양을 다포체라 부르기로 하고, 위의 수열 $p(n)$을 이 다포체의 다포체수라 부르기로 하였다.

하늘이는 다포체의 확장은 다시 다포체가 됨을 확인할 수 있었다. 따라서 한 다포체를 여러 번 잇달아 확장할 수도 있었다. 예로, 삼각형 역시 직선(크기 $n$의 직선은 직선 위에 $n$개의 점을 그린 것이다)의 확장이고, 직선은 다시 점(크기 $n$의 점은 항상 한 개의 점이다)의 확장이 된다. 그러므로 사면체는 점을 3번 확장하여 만들 수 있는 모양이 되는 것이다.

이제 하늘이는 한 다포체를 여러 번 확장하여 만든 다포체의 다포체수를 어떻게 구할 수 있을지 궁금해졌다. 하늘이를 대신하여 이를 구해 주자. 특히, 원래 다포체의 다포체수가 $d$차 다항식 $q(n)$을 따를 때, 이를 $K$번 확장하여 만든 다포체의 다포체수를 구하여 보자.

입력

첫 줄에 두 정수 $d(0\leq d\leq 1,円 000)$와 $K(1\leq K\leq 1,円 000)$가 공백을 구분으로 하여 주어진다. 다음 줄에 $q(n)$의 계수들이 공백으로 구분되어 순서대로 주어진다. 이는 각각 상수항, 일차항, 이차항, $\cdots,ドル $d$차항의 계수로서, 총 $d+1$개의 0ドル$ 이상 998ドル,244円,353円$ 미만의 정수가 주어진다. 단, $q(n)$의 $d$차항의 계수는 0이 아니다.

출력

다포체수가 $d$차 다항식 $q(n)$을 따르는 다포체에 대해, 이를 $K$번 확장하여 만든 다포체의 다포체수를 $[S^K(q)](n)$이라 하자. 한 줄에 공백을 구분으로 하여, 다항식 $[S^K(q)](n)$의 상수항, 일차항, 이차항, $\cdots,ドル 최고차항의 계수 각각을 998ドル,244円,353円$으로 나눈 나머지를 순서대로 출력한다. 유리수를 나눈 나머지는 아래에 설명되어 있다. 단, 998ドル,244円,353円$은 소수이다.

기약분수 $\frac{p}{q}(p\ge 0, q>0, \gcd(p,q)=1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1 \pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

$[S^K(q)](n)$은 유리계수 다항식임을 증명할 수 있으며, 계수 중 어느 것도 기약분수로 표현하였을 시 분모가 998ドル,244円,353円$의 배수가 되지 않음 역시 증명할 수 있다.

제한

노트

다포체를 1회 확장할 때마다 대응되는 다포체수의 차수는 1ドル$ 증가함을 확인할 수 있다. 이에 따르면, 반환되는 다항식의 차수는 $d+K$여야 한다.

이하는 엄밀성을 보강하기 위한 서술이다.

$d$차원 모양이란, 각 양의 정수 $n$마다 $\mathbb{R}^d$ 위의 유한 점집합 하나를 대응시키는 방식(scheme)을 뜻한다.

한 $d$차원 모양에 대하여, 이를 확장한 $d+1$차원 모양은 다음과 같이 ‘정의’한다 :

크기 $n$의 확장된 모양은, 공간 $\mathbb{R}^{d+1}$ 안에 $\mathbb{R}^d$의 복제본 $n$개를 평행하게 둔 뒤 각각에 크기 1ドル,ドル 2ドル,ドル $\cdots,ドル $n$의 모양을 그리고, 이를 모두 합쳐 만든 한 점집합이다.

모양의 확장은 모양을 그리는 방법이 다양하므로 단 한 가지로 정의할 수 없지만, 다포체의 확장을 어떻게 그리더라도 그 다포체수가 변화하는 일은 없으므로 사실상 다포체수가 주어진 다포체에 대해 확장된 다포체의 다포체수는 잘 정의된다. 이 문제에서는 그것으로 충분하다.