406865: GYM102586 E 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$$$

Constraints:

• $$$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.

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

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

1
0

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