高橋くんは串焼きが大好きで、現在バーベキュー場にいます。

バーベキュー場には非負整数 $A_i$ と $0$ または $1$ からなる値 $T_i$ で表される食材が $N$ 個と、最大で $M$ 個の食材を刺せる串が $1$ つあります。

あなたは高橋くんのためにできるだけおいしい串焼きを作ることにしました。

串焼きは $M$ 個以内の食材を使って作られ、そのおいしさは以下のように求められます。

• おいしさは初期値 $0$ 。
• 順に串焼きの食材を見ていき、以下のようにおいしさを更新する。
  • $T_i = 0$ のとき、おいしさに $A_i$ を足す。
  • $T_i = 1$ のとき、おいしさを $A_i$ 倍する。
• 最終的なおいしさが串焼きのおいしさとなる。

あなたが作ることのできる串焼きのおいしさの最大値を求めてください。

ただし、答えはとても大きくなる可能性があるので $998244353$ で割った余りを出力してください。

• $1 \leq N \leq 10^5$

• $0 \leq M \leq N$

• $T_i$ は $0$ または $1$

• $0 \leq A_i \leq 10^9$

• 入力は全て整数である。

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

答えを出力せよ。