Count Modulo 2

Time limit3.5sMemory limit1024 MB

Summary

Given N and a set A, count the length-N sequences of values from A that sum to S, modulo 2, with N and S up to 10^18.

Level: Medium7 of 10
Topics: Math, Dynamic programming, Number theory
Solved: No attempts yet

Problem

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

There are $T$ tests in one input file.

Input

Input is given from standard input in the following format:

$T$

The description of each test is given in the following format, one test after another.

$N$ $S$ $K$

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

Output

For each test, print the count modulo 2.

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.

Hint

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

Examples1

Example 1

Input

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

Expected output

1
0