Zero-Break

시간 제한: 1 초 / 메모리 제한: 128 MB

문제

길이가 \(n\)인 수열 \(a\)에 대하여 다음 조건을 만족하는 \(n\times m\) 크기의 행렬 \(P\)의 개수를 구하시오.

• \(1\leq i\leq n\) 이고 \(1\leq j\leq m\)인 모든 정수 \(i\), \(j\)에 대하여 \(P_{i,j}\in\{0,1\}\) 이다.
• \(1\leq i\leq n\) 인 모든 정수 \(i\)에 대하여 \(\displaystyle\sum_{j=1}^{m}P_{i,j}=a_i\) 이다.
• \(1\leq i\leq n - 2\) 이고 \(1\leq j\leq m\)인 모든 정수 \(i\), \(j\)에 대하여 \(P_{i,j}+P_{i+1,j}+P_{i+2,j}\neq3\) 이다.

입력

첫 번째 줄에 행렬의 크기를 나타내는 정수 \(n\), \(m\)이 공백을 사이에 두고 차례로 주어진다. \((1\leq n\leq200\,000,\,m\in\{4,5,6,8\})\)

두 번째 줄에 \(a\)의 원소 \(a_1, a_2, \cdots, a_n\) 이 공백을 사이에 두고 차례로 주어진다. \((0\leq a_i\leq m;\) 모든 \(a_i\)는 정수\()\)

출력

문제의 조건을 만족하는 행렬 \(P\)의 개수를 \(998\,244\,353\)으로 나눈 나머지를 출력하시오.

---

예제 입력 1

3 4
4 2 2

예제 출력 1

6

---

예제 입력 2

25 4
3 2 2 3 2 2 2 2 2 2 2 2 2 3 2 1 2 3 3 2 2 2 2 2 2

예제 출력 2

376375013

---