No.2485 Add to Variables (Another)
ytqm3
MagentorProblem Statement
There is a sequence $A$ of length $N$. Initially, all values of $A$ are $0$.
Consider performing the following $4$ types of operations on this sequence.
- Do nothing.
- Choose an integer $k \ (1 \leq k \leq N-1)$ and, for every integer $i$ satisfying $1 \leq i \leq k$, add $1$ to $A_i$.
- Choose an integer $k \ (2 \leq k \leq N)$ and, for every integer $i$ satisfying $k \leq i \leq N$, add $1$ to $A_i$.
- For every integer $i$ satisfying $1 \leq i \leq N$, add $1$ to $A_i$.
Among the ways to perform exactly $M$ operations, find the number of those resulting in $A=B$, modulo $998244353$.
Here, two sequences of operations are considered different if and only if there exists an integer $i$ such that the sets of indices of the elements to which $1$ is added in the $i$-th operation differ.
Input
The input is given from Standard Input in the following format.
$N$ $M$ $B_1$ $B_2$ $\ldots$ $B_N$
Output
Output the answer.
Sample
Sample 1
Input
4 2 1 1 1 0
Output
2
In the $1$-st operation, add $1$ to $A_1,A_2,A_3$, and in the $2$-nd operation, do not add $1$ to any variable; or, in the $1$-st operation, do not add $1$ to any variable, and in the $2$-nd operation, add $1$ to $A_1,A_2,A_3$. These $2$ ways are possible.
Sample 2
Input
4 2 1 1 1 1
Output
8$A_1=A_2=A_3=A_4=1$ can be achieved only when adding $1$ to the variables to which $1$ was not added in the $1$-st operation, so the answer is $8$ ways.
Sample 3
Input
4 3 0 3 2 2
Output
0
Sample 4
Input
4 314 202 3 9 22
Output
362672301
Sample 5
Input
1 1 1
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。