There are $n$ lamps in a row, all initially off. The show lasts for $m$ days.

On day $i$, you must choose exactly $a_i$ distinct lamps and toggle each chosen lamp: a lamp that is off becomes on, and a lamp that is on becomes off.

A plan is the sequence of chosen sets over all $m$ days. Two plans are different if there is a day on which the chosen sets differ.

Count the plans that leave exactly $r$ lamps on after day $m$, modulo $998\,244\,353$.

Input

The first line contains three integers $n$, $m$, and $r$ ($1 \le n \le 10\,000$, $1 \le m \le 200\,000$, $0 \le r \le n$).

The second line contains $m$ integers $a_1, a_2, \ldots, a_m$ ($0 \le a_i \le n$).

Output

Print a single integer: the number of plans leaving exactly $r$ lamps on after day $m$, taken modulo $998\,244\,353$.

Examples

Input 1

3 2 1
1 2

Output 1

6

Input 2

7 4 4
1 2 4 5

Output 2

57960