Exp

용사가 n마리의 몬스터를 차례로 물리칠 때 얻는 경험치의 기댓값을 구하자. 각 몬스터를 물리칠 때 용사는 확률 $p_i$로 $i$ 단위의 경험치를 독립적으로 얻는다 ($0 \le i \le k$). 다만 용사가 얻은 경험치의 총합이 $x$를 넘으면 경험치는 정확히 $x$로 잘린다. 이 기댓값을 $998\,244\,353$으로 나눈 나머지를 출력하라.

첫째 줄에 세 정수 $n$, $k$, $x$가 주어진다 ($1 \le n \le 10^7$; $1 \le k \le 100$; $1 \le x \le \min(10^7, 5 \cdot 10^7/k)$).

둘째 줄에 $k+1$개의 실수 $p_0, p_1, \ldots, p_k$가 주어진다 ($0 < p_i < 1$). 각 수는 소수점 아래 정확히 4자리로 주어진다. $p_i$의 합은 1이다.

용사가 얻을 경험치의 기댓값을 출력하라.

구하는 값을 기약분수 $p/q$로 나타낼 수 있고 $q \not\equiv 0 \pmod{998\,244\,353}$임을 보일 수 있다. 이때 $r \cdot q \equiv p \pmod{998\,244\,353}$이고 $0 \le r < 998\,244\,353$인 정수 $r$이 유일하게 존재하므로, 이 $r$을 출력한다.

첫 번째 테스트에서 용사는 확률 $1/4$로 경험치 0을, 확률 $1/2$로 경험치 1을, 확률 $1/4$로 경험치 2를 얻는다. 따라서 기댓값은 1이다.

두 번째 테스트에서 용사는 확률 $1/4$로 경험치 0을, 확률 $3/4$로 경험치 1을 얻는다. 기댓값은 $3/4$이다.