시간 제한메모리 제한제출정답맞힌 사람정답 비율
3.5 초 (추가 시간 없음) 1024 MB53360.000%

문제

You are given $K$ distinct nonnegative integers $A_1,A_2,\cdots,A_K$. Count the number of sequences of $N$ nonnegative integers $a_1,a_2,\cdots,a_N$ that satisfies all of the following conditions, modulo $2$.

  • $a_1+a_2+\cdots+a_N=S$
  • For each $i$ ($1 \leq i \leq N$), there exists an integer $j$ such that $a_i=A_j$.

Note that there are $T$ tests in one input file.

입력

Input is given from Standard Input in the following format:

$T$

Description of the 1-st test

Description of the $2$-nd test

$\vdots$

Description of the $T$-th test

The description of each test is in the following format:

$N$ $S$ $K$

$A_1$ $A_2$ $\cdots$ $A_K$

출력

For each test, print the count modulo $2$.

제한

  • $1 \leq T \leq 5$
  • $1 \leq N \leq 10^{18}$
  • $0 \leq S \leq 10^{18}$
  • $1 \leq K \leq 200$
  • $0 \leq A_1 < A_2 < \cdots < A_K \leq 10^5$
  • All values in input are integers.

예제 입력 1

2
5 10 3
1 2 3
1000000000000000000 25453321771239381 10
0 1683 21728 31623 35054 37834 39329 56842 68603 74742

예제 출력 1

1
0

노트

In the first test, there are a total of $51$ sequences that satisfy conditions.