Reconstructing f‐Sequence from Differences

An array of n infected people is lined up and numbered from \(1\) to \(n\). Each infected person has an unknown infection depth \(a_i\). A special container will start from some position \(x\) and proceed to kill all infected persons from position \(x\) to \(n\) with the following twist: whenever it kills two consecutively numbered infected persons whose infection depths are strictly increasing (i.e. if \(a_i<a_{i+1}\)), then it will skip the very next infected person (if one exists).

For each starting position \(x\) (\(1\le x\le n\)), let \(f_x\) denote the number of killed infected when the container starts at \(x\). These \(f_x\) values are produced by running the process independently for each \(x\) (that is, the simulation for each \(x\) does not affect the others). For example, if \(n=5\) and the infection depths are given by

[ 2; 6; 4; 5; 1 ]

then the corresponding (f) sequence is

[ {4,; 3,; 2,; 2,; 1}. ]

You do not know the actual infection depths \(a_i\); you are only given m values which are claimed to be some of the differences \(f_i-f_{i+1}\) (for \(1\le i\le n-1\)). (In a valid test case it holds that \(m=n-1\).)

A key observation is that the container’s killing process is uniquely determined by binary choices at positions where a decision is made: after killing infected \(i\) and \(i+1\), if the infection depths satisfy \(a_i<a_{i+1}\) the container skips infected \(i+2\); otherwise it does not. If we forget the actual depths and only record this binary decision, one may prove that the final \(f\) sequence is given by the following recurrence (we adopt the convention that if an index is out‐of–range then \(f_i=0\)):

[ \begin{array}{ll} f(n)=1,\quad & f(n-1)=2,\[1mm] \text{for }1\le i\le n-2:\quad & f(i)=\begin{cases}2+f(i+2) &\text{if the decision at }i \text{ is }0,\[1mm]2+f(i+3) &\text{if the decision at }i \text{ is }1, (\text{with the convention that if }i+3>n\text{ then }f(i)=2).\end{cases} ]

Thus the differences \(d_i=f(i)-f(i+1)\) are completely determined by the binary decisions. In fact, a short computation shows that when the sequence \(f(1),f(2),\dots,f(n)\) is recovered from the differences \(d_1,d_2,\dots,d_{n-1}\), one must have

[ f(1)=2+\sum_{i=1}^{n-2}d_i,\quad f(i+1)=f(1)-\sum_{j=1}^{i}d_j,\quad \text{with } f(n-1)=2 \text{ and } f(n)=1. ]

The recurrence forces further constraints. In particular, for every \(1\le i\le n-2\) the value \(f(i)\) must be equal to either \(2+f(i+2)\) or \(2+f(i+3)\) (if \(i+3\le n\), or \(2\) if \(i+3>n\)). Rewriting these conditions in terms of the given differences \(d_i\) one may show that for every \(1\le i\le n-2\) one must have

• For \(1\le i\le n-3\): either
  \(d_i+d_{i+1}=2\) or \(d_i+d_{i+1}+d_{i+2}=2\).
• For \(i=n-2\): either \(d_{n-2}+d_{n-1}=2\) or \(d_{n-2}=0\) (the latter comes from the convention for indices out of range).

Your task is: given the m values \(d_1,d_2,\dots,d_m\) (with \(m=n-1\)), count how many different \(f\) sequences (that is, how many different valid assignments of the binary decisions) are possible. (Recall that two \(f\) sequences \(f\) and \(g\) are considered different if and only if there is an index \(1\le i\le n\) with \(f(i)\neq g(i)\).

Since the answer can be large, output it modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(m\) (where it is guaranteed that \(m=n-1\)).

The second line contains \(m\) integers \(d_1,d_2,\dots,d_m\), which are the given values \(f_i-f_{i+1}\) for \(1\le i\le n-1\). It is guaranteed that \(d_m=1\) (since \(f(n-1)=2\) and \(f(n)=1\)).

outputFormat

Output a single integer, the number of distinct \(f\) sequences that are consistent with the given differences, modulo \(998244353\).

sample

2 1
1

1