일렬로 늘어선 $n$개의 램프가 있으며, 처음에는 모두 꺼져 있다. 공연은 $m$일 동안 진행된다.

$i$번째 날에는 서로 다른 램프를 정확히 $a_i$개 골라 선택한 각 램프의 상태를 뒤집어야 한다. 꺼진 램프는 켜지고, 켜진 램프는 꺼진다.

계획은 $m$일 전체에 걸쳐 선택한 집합들의 수열이다. 선택한 집합이 서로 다른 날이 하나라도 있으면 두 계획은 서로 다르다.

$m$번째 날이 끝난 뒤 정확히 $r$개의 램프가 켜져 있게 하는 계획의 수를 $998\,244\,353$으로 나눈 나머지를 구하여라.

입력

첫 번째 줄에는 세 정수 $n$, $m$, $r$이 주어진다 ($1 \le n \le 10\,000$, $1 \le m \le 200\,000$, $0 \le r \le n$).

두 번째 줄에는 $m$개의 정수 $a_1, a_2, \ldots, a_m$이 주어진다 ($0 \le a_i \le n$).

출력

$m$번째 날이 끝난 뒤 정확히 $r$개의 램프가 켜져 있게 하는 계획의 수를 $998\,244\,353$으로 나눈 나머지를 정수 하나로 출력하여라.

예제

입력 1

3 2 1
1 2

출력 1

6

입력 2

7 4 4
1 2 4 5

출력 2

57960