23480번 - 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.