시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB50171126.829%

## 문제

Find the expected amount of experience a hero will get for beating n monsters one by one, given that beating each monster gives the hero i units of experience (0 ≤ i ≤ k) with probability pi independently, but if the hero gets more than x units of experience in total, their experience is capped to exactly x units, and display it modulo 998 244 353.

## 입력

The first line contains three integers n, k, and x (1 ≤ n ≤ 107; 1 ≤ k ≤ 100; 1 ≤ x ≤ min(107, 5·107/k)).

The second line contains k + 1 real numbers p0, p1, . . . , pk (0 < pi < 1), given with exactly 4 decimal digits. The sum of pi is equal to 1.

## 출력

Display the expected amount of experience the hero will get.

It can be shown that the sought number can be represented as an irreducible fraction p/q such that q ≢ 0 (mod 998 244 353). Then, there exists a unique integer r such that r · q ≡ p (mod 998 244 353) and 0 ≤ r < 998 244 353, so display this r.

## 예제 입력 1

2 1 2
0.5000 0.5000


## 예제 출력 1

1


## 예제 입력 2

2 1 1
0.5000 0.5000


## 예제 출력 2

249561089


## 예제 입력 3

4 2 5
0.2000 0.5000 0.3000


## 예제 출력 3

909700083


## 예제 입력 4

10 4 23
0.4533 0.2906 0.1618 0.0071 0.0872


## 예제 출력 4

433575862


## 힌트

In the first test case, the hero will get 0 units of experience with probability 1/4, 1 unit of experience with probability 1/2, and 2 units of experience with probability 1/4. Hence, the expected amount is 1.

In the second test case, the hero will get 0 units of experience with probability 1/4, and 1 unit of experience with probability 3/4. The expected amount is 3/4.