#P18114. Flipping Lamps

Flipping Lamps

Flipping Lamps

有 nn 盏可区分的灯排成一行,最初全部熄灭。一共进行 mm 天操作,第 ii 天必须恰好选出 aia_i 盏不同的灯,把它们的状态全部翻转。

一种计划由每天所选的灯集合依次组成;只要某一天的集合不同,就是不同计划。求第 mm 天结束后恰有 rr 盏灯亮着的计划数量,对998244353取模。

输入格式

第一行三个整数 n,m,rn,m,r,满足 1≤n≤100001\le n\le10000、1≤m≤2000001\le m\le200000、0≤r≤n0\le r\le n。

第二行 mm 个整数 aia_i,0≤ai≤n0\le a_i\le n。

输出格式

输出计划数量模998244353。

样例1

3 2 1
1 2
6

样例2

7 4 4
1 2 4 5
57960