TUNA2026 東京Stage Welcome コンテスト (オープン) 2026/09/23 14:00 ~ 2026/09/23 18:00 4:00:00

L Jutan

問題
制限時間: 2 sec メモリ制限: 256 MB
Jutan
Statement

dokukinokoさんは，\(K+1\) 枚の絨毯\(1,\ldots,K+1\) をすべて，左から順に並んだ \(N\) 個のマス \(1,\ldots,N\) に敷くことにしました． 絨毯 \(i\) は長さ \(A_i\) であり，連続する \(A_i\) 個のマスを覆うように敷くことができます．

dokukinokoさんは赤い絨毯や青い絨毯，茶色の絨毯から灰色の絨毯まで，ありとあらゆる色とりどりの絨毯をこよなく愛していますが，黒い絨毯だけは大嫌いです． そして，不幸にも絨毯 \(K+1\) は黒い絨毯です．

そこで，まず黒い絨毯を敷き，その上から他の絨毯を重ねることで，黒い絨毯が一切見えないようにしたいと考えました． ただし，黒い絨毯以外の絨毯同士が重なってしまうのは困ります．

このような条件を満たす絨毯の敷き方は何通りあるか求めてください．

厳密には，以下の条件をすべて満たすような絨毯の敷き方の個数を \(998244353\) で割った余りを求めてください．

  • 絨毯 \(1,\ldots,K+1\) がすべて敷かれている．
  • 各絨毯はマスの線に沿って置かれ，マス列からはみ出してはならない．
  • 絨毯 \(K+1\) に覆われているすべてのマスは，他の絨毯のうちちょうど \(1\) 枚によって覆われている．
  • 絨毯 \(K+1\) に覆われていないすべてのマスは，他の絨毯のうち高々 \(1\) 枚によって覆われている．

ただし，絨毯は番号によって区別されます． また，いずれかの絨毯の左端の位置が異なる場合，それらは異なる敷き方として数えます．

Input

  • 1行目に\(N,K\)(\(1\leq N \leq 500,1 \leq K \leq N\))が空白区切りでこの順に与えられます．
  • 2行目に数列\(A_1,\ldots,A_{K+1}(1 \leq A_i \leq N,A_1 + A_2 + \cdots + A_K \leq N)\)が空白区切りにこの順で与えられます．
  • 入力は全て整数であることが保証されています．

Output

条件を満たすような絨毯の敷き方の個数を \(998244353\) で割った余りを出力してください．

Examples

Input 1
4 2
2 1 2
Output 1
10
Input 2
19 5
1 1 4 5 1 4
Output 2
456192

サンプル