술고래

그는 모든 면에서 긍정적인 사람이다. 단, 매일 저녁 술집에 간다는 점만 빼고...

당신의 친구 중 한 명은 도시에서 가장 유명한 (그리고 유일한) 술집의 바텐더다. 도시에는 $2 \cdot n + 1$채의 집이 하나의 긴 도로를 따라 늘어서 있고, $0$번부터 $2 \cdot n$번까지 번호가 붙어 있다. 술집은 $n$번 집에 있다.

흥미로운 사실은 도시의 모든 술고래가 같은 습관을 가진다는 것이다. 물론 그들은 집으로 곧장 갈 수 없는 상태로 술집을 나서므로, 목적 없이 걷기 시작한다. 즉, 모든 술고래는 머릿속에 길이 $n$인 배열 $a$를 하나씩 품고 있다. 술집을 나선 뒤 $i$번째 초에 술고래는 도로에서 자신의 위치를 $a_i$만큼 바꾸고 싶어 한다($|a_i| = 1$). 술고래가 $j$번 집 앞에 있었다면, 이 변화 후에는 $j + a_i$번 집 앞에 있게 된다.

그러나 그들은 너무 취해서 매 초 확률 $\frac{p}{100}$로 움직이지 못하고 현재 위치에 머문다.

술고래가 자기 집 앞에 도착하면, 가족들이 그를 보고 집으로 데려간다. 그가 $n$번 집 자체에 산다면, 가족들이 즉시 그를 데려갈 것이다. 그러나 $n$초가 지난 뒤에도 데려가지 않으면, 술고래는 실망해서 길에서 잠이 든다.

또 다른 술고래가 술집에 왔다. 바텐더는 그가 어디 사는지 모르므로, 모든 집에 대해 그 술고래가 그곳에 살 확률이 $\frac{1}{2 \cdot n + 1}$이라고 그냥 가정한다. 가족들이 그를 집으로 데려갈 확률을 $998\,244\,353$으로 나눈 나머지를 계산하시오.

첫 번째 줄에는 문제 설명에 나온 두 정수 $n$과 $p$가 주어진다($1 \leq n \leq 5000$, $0 \leq p \leq 100$).

두 번째 줄에는 $n$개의 정수 $a_1, \ldots, a_n$이 주어진다($|a_i| = 1$). 이는 $i$번째 초에 술고래가 하려는 움직임이다.

정수 하나를 출력한다. 답을 $998\,244\,353$으로 나눈 나머지이다.

형식적으로, $M = 998\,244\,353$이라 하자. 답은 기약분수 $\frac{p}{q}$로 나타낼 수 있으며, $p$와 $q$는 정수이고 $q$가 $M$으로 나누어떨어지지 않음이 보장된다. $p \cdot q^{-1} \bmod M$과 같은 정수를 출력하시오. 즉, $0 \leq x < M$이고 $x \cdot q = p \pmod{M}$인 정수 $x$를 출력하시오.