問題文

ある家では、$K$ 日間のパーティが行われる予定であり、$N$ 人の人が招待されています。 はじめ、$N$ 人の人は家の中で横一列に並んでいて、左から $i$ 番目 $(1\le i\le N)$ の人を人 $i$ と呼ぶことにします。

$K$ 日間のパーティについて、$d$ 日目 $(1\le d\le K)$ のパーティは以下のように行われる予定です。

• $d$ 日目の時点で家に残っている人が、それぞれ独立に「帰る」「帰らない」の一方を選択する。
• 「帰る」を選択した人のうち、以下のいずれかの条件を満たす人は家から退出する。それ以外の人はそのまま家に留まる。
  • 自分より右側に「帰らない」を選択した人が存在しない。
  • 自分より左側に「帰らない」を選択した人が存在しない。
• この時点で、家に残っている人全員で $d$ 日目のパーティを行う。

なお、パーティのどの時点においても、家にいる人どうしの相対順序が変化することはありません。

ところで、途中でパーティの参加者が１人ぼっちになってしまったり、 $K$ 日分の用意があるのに途中で全員帰ってしまうのは非常に悲しいことです。 そこで、$K$ 日間一連のパーティの成功度を、以下のように定めます。

• $K$ 日間全てのパーティが２人以上で行われた場合
  • 人 $i$ が $K$ 日間でパーティに参加した日数を $D_i$ として、成功度は $\displaystyle\sum_{i=1}^{N}A_i^{D_i}$ とする。
• $K$ 日間のうち１日以上で、パーティの参加人数が１人以下になってしまった場合
  • 成功度は、$0$ とする。

さて、$K$ 日間のパーティの行われ方は、各日における人の「帰る」「帰らない」の選択方法によって定まります。 そこで、考えうる全ての選択方法に対して、結果行われる $K$ 日間のパーティの成功度を計算しその合計を $998244353$ で割ったあまりを求めてください。

２つの選択方法が異なるとは、ある整数 $i$ および $d$ が存在して、$d$ 日目に人 $i$ が行った選択が異なることとします。

ここで、家から退出した人はそれ以降選択を行わないことに注意してください。

入力

$N\ \ K$
$A_1\ \ A_2\ \cdots \ A_N$

• $2\le N\le 10^5$
• $1\le K\le 14$
• $1\le A_i\lt 998244353$
• 入力は全て整数

出力

答えを $\bmod{998244353}$ で出力せよ。

サンプル

3 1
1 2 4

25

2 14
2997 92458

660248434

5 7
662 60 70 15 1034

156455438