Exp

Time limit5sMemory limit512 MB

Summary

Each of n independent monsters grants i experience (0 to k) with probability p_i, totals are capped at x, and the expected capped total must be computed modulo 998244353.

Level: Hard8 of 10
Topics: Probability, Dynamic programming, Math, Prefix sum
Solved: No attempts yet

Problem

Find the expected amount of experience a hero gets for beating $n$ monsters one by one. Beating each monster gives the hero $i$ units of experience ( $0 \le i \le k$ ) with probability $p_i$ , independently across monsters. If the hero's total experience exceeds $x$ , it is capped to exactly $x$ . Display the expected amount modulo $998\,244\,353$ .

Input

The first line contains three integers $n$ , $k$ , and $x$ ( $1 \le n \le 10^7$ ; $1 \le k \le 100$ ; $1 \le x \le \min(10^7, 5 \cdot 10^7/k)$ ).

The second line contains $k+1$ real numbers $p_0, p_1, \ldots, p_k$ ( $0 < p_i < 1$ ), given with exactly 4 decimal digits. The sum of $p_i$ is 1.

Output

Display the expected amount of experience the hero gets.

It can be shown that the sought number can be written as an irreducible fraction $p/q$ with $q \not\equiv 0 \pmod{998\,244\,353}$ . Then there is a unique integer $r$ such that $r \cdot q \equiv p \pmod{998\,244\,353}$ and $0 \le r < 998\,244\,353$ , so display this $r$ .

Hint

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

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

Examples4

Example 1
Input
```
2 1 2
0.5000 0.5000
```
Expected output
```
1
```
Example 2
Input
```
2 1 1
0.5000 0.5000
```
Expected output
```
249561089
```
Example 3
Input
```
4 2 5
0.2000 0.5000 0.3000
```
Expected output
```
909700083
```

Example 4

Input

10 4 23
0.4533 0.2906 0.1618 0.0071 0.0872

Expected output

433575862