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.