가챠폰

위키백과에 따르면, "가챠 게임은 가챠(장난감 자판기) 메커니즘을 구현한 비디오 게임이다." 루트박스와 비슷하게, 가챠 게임은 플레이어가 게임 내 재화를 써서 무작위 가상 아이템을 얻도록 유도한다.

스텝업 가챠라는 가챠 게임이 있다. 플레이어가 뽑을 때마다 희귀 아이템을 뽑을 확률이 올라간다. 예를 들어 원신은 연속된 10번의 뽑기 안에서 항상 4성 아이템이나 캐릭터를 뽑을 수 있도록 보장한다.

이런 뽑기 규칙을 추상화하면 도움이 된다. $0$성, $1$성, $\ldots$, $m$성 아이템이 있는 게임을 생각하자. 한 번 뽑을 때 $i$성 아이템이 나올 확률은 $\frac{a_i}{\sum_{j=0}^{m} a_j}$이다. 한 번 뽑는 것을 레벨 $0$ 뽑기라고 한다. 레벨 $k$ 뽑기는 레벨 $(k-1)$ 뽑기를 정확히 $b_k$번 수행하는 것이다. 뽑기의 최고 레벨은 $n$이다.

레벨 $k$ 뽑기가 다음 조건을 보장하면 유효(legal)하다고 한다.

• 적어도 한 개의 $k$성 이상 아이템이 뽑힌다.
• 포함된 $b_k$개의 레벨 $(k-1)$ 뽑기 각각에서 적어도 한 개의 $(k-1)$성 이상 아이템이 뽑힌다.
• 같은 방식으로 레벨 $0$ 뽑기(한 번 뽑기)까지 내려간다. 레벨 $0$에서는 0성 이상 아이템이 뽑히는 것이 자명하게 성립한다.

$p_i$를 유효한 $n$레벨 뽑기에서 뽑힌 $i$성 아이템 개수의 기댓값이라 하고, $q$를 $n$레벨 뽑기가 유효할 확률이라 하자. $p_i$와 $q$의 값을 구하라. 큰 수와 0으로 나누는 문제를 피하려고, 모든 $0 \le i \le m$에 대해 $(p_i \cdot q) \bmod 998\,244\,353$ 값만 출력한다.

첫 줄에 최대 성 수 $m$과 뽑기의 최고 레벨 $n$, 두 정수가 주어진다($1 \le n \le m \le 4000$).

둘째 줄에 $m+1$개의 정수 $a_0, a_1, \ldots, a_m$이 주어진다. $a_i$는 $i$성 아이템을 뽑는 빈도이다($1 \le a_i \le 4000$).

셋째 줄에 $n$개의 정수 $b_1, b_2, \ldots, b_n$이 주어진다. $b_k$는 레벨 $k$ 뽑기 한 번에 포함되는 이전 레벨 뽑기의 개수이다($2 \le b_k \le 4000$).

$m+1$줄을 출력한다. $i$번째 줄에는 $(p_{i-1} \cdot q) \bmod 998\,244\,353$ 값을 정수 하나로 출력한다.

첫 번째 예제에서 유리수 형태로 나타낸 답은 $\frac{8}{9}$, $1$, $1$이다.