2로 나눈 나머지 개수 세기

$K$개의 서로 다른 음이 아닌 정수 $A_1, A_2, \cdots, A_K$가 주어진다. 다음 조건을 모두 만족하는 길이 $N$의 음이 아닌 정수 수열 $a_1, a_2, \cdots, a_N$의 개수를 2로 나눈 나머지를 구하라.

• $a_1+a_2+\cdots+a_N=S$
• 각 $i$ ($1 \leq i \leq N$)에 대해 $a_i=A_j$를 만족하는 정수 $j$가 존재한다.

입력 파일 하나에는 $T$개의 테스트가 있다.

입력은 표준 입력으로 다음 형식에 따라 주어진다.

$T$

각 테스트는 다음 형식으로 주어지며, 테스트마다 이 형식이 이어진다.

$N$ $S$ $K$

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

각 테스트에 대해 개수를 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$
• 입력의 모든 값은 정수이다.

첫 번째 테스트에서 조건을 만족하는 수열은 총 51개이다.