Given an array $$$A$$$ of length $$$N$$$, whose elements are $$${A_1}, {A_2}, \ldots, {A_N}$$$, its array of $$$K$$$-sums blocks is defined as the array of length $$$N-K+1$$$ that satisfies $$$$$$B_i = A_i + A_{i+1} + \cdots + A_{i+K-1}$$$$$$
For example, for $$$A = [0,1,1,0,1]$$$, its array of $$$4$$$-sums blocks is $$$B = [2, 3]$$$, since $$$B_1 = 0 + 1 + 1 + 0 = 2$$$ and $$$B_2 = 1 + 1 + 0 + 1 = 3$$$.
Given an array $$$B$$$ of length $$$N-K+1$$$, count how many arrays $$$A$$$ of length $$$N$$$ exist such that their array of $$$K$$$-sums blocks is $$$B$$$. Both $$$B$$$ and the possible arrays $$$A$$$ consist of non-negative integers. Since the number of arrays $$$A$$$ can be very large, the answer must be given modulo $$$998244353$$$.
Note that the sums of the $$$K$$$-sums blocks array are exact and not modular, meaning the modulo should only be applied to the answer.
The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq K \leq N \leq 2 \cdot 10^5$$$).
The second line contains $$$N-K+1$$$ integers $$${B_1}, {B_2}, \ldots, {B_{N-K+1}}$$$ ($$$0 \leq B_i \leq 10^9$$$), the elements of the array $$$B$$$.
A line with an integer indicating the number (modulo $$$998244353$$$) of possible arrays $$$A$$$ formed by non-negative integers such that $$$B$$$ is their array of $$$K$$$-sums blocks.
5 4 2 3
10
6 1 2 3 0 8 2 5
1
2 2 1000000000
1755648
In the first example, there are $$$10$$$ possible arrays $$$A$$$. These are $$$[0,1,1,0,1]$$$, $$$[1,0,1,0,2]$$$, $$$[0,0,1,1,1]$$$, and $$$7$$$ other arrays.
In the second example, the only possible array is $$$[2, 3, 0, 8, 2, 5]$$$.
In the third example, remember that the answer must be given modulo $$$998244353$$$.
