Count Modulo 2

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.

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