The classic problem

there are $N$ items,which has values from 0 to $N-1$,find a subset of the items(you can choose nothing),you need to make the sum of the subset
$S\equiv 0(mod~M)$

what's more,we make the rule that $K$ values $(a_1,a_2..a_K)$cannot be chosen.

please output the number of ways module 998244353

the first line contains a number $T$,means the number of the test cases.

next,for each test case,the first line contains three numbers,$N,M,K$.

next line contains $K$ distinct numbers,$a_1,a_2..a_K$,means the numbers cannot be chosen.

$T\le 200,N\le 10^9,m\le 2048,K\le 4000$,$M$ is the Power of 2.

Only for 4 test cases there are $m>200$.

$T$ lines,for each test case,output the answer.

1
6 8 1
2

6

six ways:
$0+1+3+4=8$
$1+3+4=8$
$0+3+5=8$
$3+5=8$
$0$
choose nothing($S=0$)

BestCoder Round #68 (div.1)