Hay $n$ lámparas en fila, todas apagadas inicialmente. El espectáculo dura $m$ días.

En el día $i$, debes elegir exactamente $a_i$ lámparas distintas y cambiar el estado de cada lámpara elegida: una lámpara apagada se enciende y una lámpara encendida se apaga.

Un plan es la secuencia de conjuntos elegidos a lo largo de los $m$ días. Dos planes son diferentes si hay un día en el que los conjuntos elegidos difieren.

Cuenta los planes que dejan exactamente $r$ lámparas encendidas después del día $m$, módulo $998\,244\,353$.

Entrada

La primera línea contiene tres enteros $n$, $m$ y $r$ ($1 \le n \le 10\,000$, $1 \le m \le 200\,000$, $0 \le r \le n$).

La segunda línea contiene $m$ enteros $a_1, a_2, \ldots, a_m$ ($0 \le a_i \le n$).

Salida

Imprime un único entero: el número de planes que dejan exactamente $r$ lámparas encendidas después del día $m$, módulo $998\,244\,353$.

Ejemplos

Entrada 1

3 2 1
1 2

Salida 1

6

Entrada 2

7 4 4
1 2 4 5

Salida 2

57960