공평한 사다리타기 게임

싸이버거와 대회 참가자간의 매칭을 계산하는 것은 꽤나 복잡한 작업이다. 관련하여, 제비뽑기라 불리우는 heuristic decision processing이 앞선 상황 등에서 효율적일 때가 많으며 일례로 '사다리타기 게임'을 떠올릴 수 있겠다.

가장 일반적인 형태의 '사다리타기 게임' 규칙은 이렇다: 평면 위에 참가자의 수만큼 세로줄을 평행하게 긋고, 인접한 세로줄 사이에 가로줄들을 무작위로 긋는다. 이후 각 참가자들은 배정된 세로줄의 위에서부터 아래로 이동하되 가로줄을 만날 때마다 그 인접 세로줄로 넘어간다. 최종 결과는 각 세로줄의 바닥에 위치한다.

우리는 정말로 위의 규칙으로부터 각 참가자들에 대해 확률적으로 균일한 결과를 기대할 수 있을까? 참가자와 세로줄의 배열 순서에 따른 분포 편향은 없는가? 또 만일 참가자들이 세로줄을 직접 선택할 수 있다면? 혹은 완벽히 제삼자가 되어야할 가로줄을 긋는 인물이 누군가의 부정한 청탁을 받아들인다면?

이에 rootenter는 보다 공정하면서도 그 결과의 예측 가능성을 배제할 아래와 같은 '공평한 사다리타기 게임'을 제안한다.

• $N$명의 참가자 각각에 대응하도록 우선 $N$개의 세로줄을 원형으로 긋는다. 편의를 위해 초기에 $n$번 참가자에게 배정된 세로줄을 '$n$번-세로줄'이라 부르자. $(1 \leq n \leq N)$
• 이후 사전에 주어진 길이 $N-1$의 수열 $\{A_n\}$에 따라 $m$개의 가로줄을 하나씩 그어 내려간다. 그 규칙은 다음과 같다:
  • 먼저 $N$개의 세로줄 중 하나를 무작위로 선택한다. 여기서 $i$번-세로줄이 선택되었다고 하자.
  • 이어서 $i$번-세로줄과 연결할 $j$번-세로줄을 선택한다. $j$번-세로줄은 $i$번-세로줄과의 '거리'를 고려하여 $\frac{A_{|j-i|}}{\sum_{n=1}^{N-1}A_n}$의 확률로 선택된다. 이때, 입력에서 $A_{N-|j-i|} = A_{|j-i|}$임은 보장된다. (단, $i \neq j$.)

하지만 rootenter는 자신이 고안한 게임의 정당성을 증명해야한다. 그의 주장에 따르면 '공평한 사다리타기 게임'의 정당성을 보이는 과정에서 다음의 값을 계산해보는 것이 도움이 될 것이라 한다:

대충 임의의 참가자가 사다리를 타고 내려왔을 때 여전히 출발했을 때의 세로줄에 있을 확률을 알면 좋을것같은뎅슝

그러고는 그 작업을 당신에게 떠넘긴다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $A_1\ A_2\ \cdots\ A_{N-1}$

$M$개의 정수를 한 줄에 공백으로 구분하여 출력한다.

$i$번째 정수는 $m=i$일 때 출발 세로줄과 도착 세로줄이 같은 참가자 수의 기댓값을 $998\ 244\ 353$으로 나눈 나머지에 해당한다.

기댓값이 유리수 $\frac pq$이고 $q \not\equiv 0 \pmod{998\ 244\ 353}$라면, 그 값을 $p q^{-1} \bmod 998\ 244\ 353$으로 출력한다.

• $2 \leq N \leq 500\ 000$. (단, $N$은 $998\,244\,352$의 약수임이 보장된다.)
• $1 \leq M \leq 1\ 000\ 000$.
• $1 \leq A_d \leq 998\ 244\ 352$ ($1 \leq d \leq N-1$).
• $\sum_{d=1}^{N-1}A_d \not\equiv 0 \pmod{998\ 244\ 353}$.