격자 경로의 가중치

$K \leq t \leq N$인 모든 정수 $t$에 대하여, 좌표평면 위의 격자점 $(0,0)$에서 출발해 다음 규칙에 따른 행동을 원하는 횟수만큼 시행해 격자점 $(t,t)$에 도착하는 경로를 생각해 보자.

• $x \gt y$인 점 $(x,y)$에서는 $(x+1,y)$ 또는 $(x,y+1)$로 이동할 수 있다.
• $x \leq y$인 점 $(x,y)$에서는 $(x+K,y+K-1)$로 이동할 수 있다.

좌표평면 위의 직선 $y=x$ 상에 있는 격자점 $(i,i)$는 가중치 $a\_i$를 가진다. 한 경로의 가중치는 경로에 포함된 직선 $y=x$ 상에 있는 모든 격자점의 가중치의 곱으로 정의한다.

점 $(0,0)$에서 출발해 점 $(t,t)$에 도착하는 서로 다른 경로의 가중치의 합을 구하여라. 경로에 포함된 점의 집합이 일치하지 않으면 다른 격자 경로이다.

첫째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200\\,000)$

둘째 줄에 $N+1$개의 정수 $a\_0$, $a\_1$, $\cdots$, $a\_{N}$이 공백으로 구분되어 주어진다. $(0 \leq a\_i \lt 998\\,244\\,353)$

$K \leq t \leq N$인 모든 정수 $t$에 대하여, 첫째 줄에 점 $(0,0)$에서 출발해 행동을 원하는 횟수만큼 시행해 점 $(t,t)$에 도착하는 서로 다른 격자 경로의 가중치의 합을 $998\\,244\\,353$로 나눈 나머지를 공백으로 구분하여 출력한다.