题目描述

宝可梦保护协会致力于保护全球各地的宝可梦及其栖息地。在最近的研究中，研究人员收集了 $h$ 个栖息地的数据。

每个栖息地可能栖息着若干种宝可梦。研究人员知道每种宝可梦的肢体数量。由于宝可梦行动敏捷且极善隐藏，研究人员只能检测到每个栖息地的肢体总数。

研究人员明白可能无法确定每种宝可梦的具体数量，但希望了解剩余的不确定性有多少。有多少种不同的宝可梦组合会产生观察到的肢体数量？

输入格式

第一行包含一个整数 $h$（$1 \le h \le 1\,024$）——栖息地的数量。 接下来的 $h$ 行描述每个栖息地。

每行以两个整数 $t$ 和 $s$（$0 \le t \le 10^9$，$1 \le s \le 3$）开头，其中 $t$ 是肢体总数，$s$ 是该栖息地的宝可梦种类数。随后是 $s$ 个整数 $l_i$（$1 \le l_i \le 16$）——每种宝可梦的肢体数量。

输出格式

输出每个栖息地可能的宝可梦组合数量。 输出应包含 $h$ 行，每行一个整数。

3
6 1 3
6 2 2 3
6 3 1 2 3

1
2
7

4
1000000000 3 1 1 1
0 3 2 4 5
17 2 2 4
34 3 5 3 2

500000001500000001
1
0
25

提示

为了举例说明，我们将使用 $\LaTeX{}$ 宝可梦：$\c{O}$ 有 1 个肢体，$\angle$ 有 2 个肢体，$\exists$ 有 3 个肢体。在第一个样例中，所有三个栖息地都有 $6$ 个肢体。

在第一个样例中，第一个栖息地只有一种宝可梦——$\exists$。因此可能是由 $\exists\exists$ 组成的年轻家庭。

第二个栖息地有两种宝可梦：$\angle$ 和 $\exists$。因此可能是 $\angle\angle\angle$ 或 $\exists\exists$。

第三个栖息地可能包含三种宝可梦中的任意一种：$\c{O}$、$\angle$ 和 $\exists$。共有七种可能的组合：$\exists\exists$、$\angle\angle\angle$、$\c{O}\angle\exists$、$\c{O}\c{O}\angle\angle$、$\c{O}\c{O}\c{O}\exists$、$\c{O}\c{O}\c{O}\c{O}\angle$、$\c{O}\c{O}\c{O}\c{O}\c{O}\c{O}$。

在第二个样例中，第一个栖息地有三种宝可梦，但它们的肢体数都是 1：$\partial$、$\c{O}$ 和 $\rho$。共有 $10^9$ 个肢体和 $\sum_{i=0}^{i\le 10^9}(i + 1)$ 种组合。

第二个栖息地没有检测到肢体。因此该区域不幸地没有宝可梦存在。

第三个栖息地的所有宝可梦都有偶数个肢体，因此不可能有 17 个肢体。

翻译由 DeepSeek V3 完成