给定 $K$ 个不同的非负整数 $A_1, A_2, \dots, A_K$。请计算满足以下所有条件的非负整数序列 $a_1, a_2, \dots, a_N$ 的个数，结果对 $2$ 取模：

• $a_1 + a_2 + \dots + a_N = S$
• 对于每个 $i$ ($1 \le i \le N$)，都存在一个整数 $j$ 使得 $a_i = A_j$。

注意：一个输入文件中包含 $T$ 组测试数据。

输入格式

输入通过标准输入按以下格式给出：

$T$ 第 1 组测试数据的描述 第 2 组测试数据的描述 ... 第 $T$ 组测试数据的描述

每组测试数据的描述格式如下：

$N \ S \ K$ $A_1 \ A_2 \dots A_K$

数据范围

• $1 \le T \le 5$
• $1 \le N \le 10^{18}$
• $0 \le S \le 10^{18}$
• $1 \le K \le 200$
• $0 \le A_1 < A_2 < \dots < A_K \le 10^5$
• 输入中的所有值均为整数。

输出格式

对于每组测试数据，输出满足条件的序列个数对 $2$ 取模的结果。

样例

样例输入 1

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

样例输出 1

1
0

说明

在第一组测试数据中，共有 $51$ 个满足条件的序列。