北海道大学にはお化けが $S$ 体います。それぞれのお化けには色と形が定められています。
お化けの色は $N$ 種類存在し、 $1$ から $N$ までの番号が付けられています。$i$ 番目の色をもつお化けは $A_i$ 体います。したがって、 $S = \sum\limits_{1 \leq i \leq N}A_i$ です。また、お化けの形は $S$ 種類存在し、全てのお化けは互いに相異なる形をもっています。

北海道大学では、色と形を選ぶことで、選んだ色と形をもつお化けが描かれているカードを $1$ 枚入手することができます。このとき、$N$ 種類の色のうち、いずれか $1$ つの色を選ぶことができます。また、$S$ 種類の形のうち、いずれか $1$ つの形を選ぶことができます。色と形のどちらも同じお化けが描かれているカードは区別しません。

あなたはちょうど $M$ 枚のカードを入手した後、お化けを キャッチ します。あるお化けは以下の $2$ つの条件の両方を満たすとき、またそのときに限りキャッチできます。

• 入手した $M$ 枚のカードの中に、同じ色をもつお化けが描かれたカードが存在しない。
• 入手した $M$ 枚のカードの中に、同じ形をもつお化けが描かれたカードが存在しない。

$S$ 体のお化けのうち、ちょうど $1$ 体のお化けをキャッチできるような $M$ 枚のカードの組の個数を $998244353$ で割った余りを求めてください。

• $1 \leq N \leq 50$
• $1 \leq M \leq 10^5$
• $1 \leq A_i \leq 40$
• $S = \sum\limits_{1 \leq i \leq N}A_i$
• 入力はすべて整数である。

• set1 $(40$ 点$)$： $S \leq 18$
• all $(60$ 点$)$：追加の制約はない

入力は以下の形式で標準入力から与えられます。

答えを出力してください。