$n$ 個のランプが一列に並んでおり、最初はすべて消灯しています。ショーは $m$ 日間続きます。

$i$ 日目には、ちょうど $a_i$ 個の異なるランプを選び、選んだ各ランプの状態を反転させなければなりません。消灯しているランプは点灯し、点灯しているランプは消灯します。

計画とは、$m$ 日間にわたって選ぶ集合の列です。選ぶ集合が異なる日がある場合、2 つの計画は異なるものとします。

$m$ 日目の終了後にちょうど $r$ 個のランプが点灯している計画の数を、$998\,244\,353$ を法として求めてください。

入力

1 行目には 3 つの整数 $n, m, r$ ($1 \le n \le 10\,000$, $1 \le m \le 200\,000$, $0 \le r \le n$) が含まれます。

2 行目には $m$ 個の整数 $a_1, a_2, \ldots, a_m$ ($0 \le a_i \le n$) が含まれます。

出力

$m$ 日目の終了後にちょうど $r$ 個のランプが点灯している計画の数を、$998\,244\,353$ を法として、1 つの整数として出力してください。

入出力例

入力 1

3 2 1
1 2

出力 1

6

入力 2

7 4 4
1 2 4 5

出力 2

57960