题目描述

考虑以下这个植物大战僵尸游戏的变体：

现在有 $N$ 个僵尸想来吃掉主角的脑子，其中第 $i$ 个僵尸与房屋的距离为 $a_{i}$，它的坐标为 $\left(0, a_{i}\right)$。

这个游戏是回合制的，地图中有两个赛道（即，地图可以认为是 $2 \times \infty$ 的棋盘，同一个位置可能有多个僵尸）。

每一回合中，以下三件事情按顺序发生：

• 游戏 AI 先行动，它可以选择把一些还活着的僵尸上下移动 (也即，从 $(0, y)$ 移动到 $(1, y)$ 或者反之）。

• 玩家行动, 玩家会得到一个火爆辣椒，他可以把火爆辣椒放在第 $0$ 行或者第 $1$ 行，消灭这一行的所有僵尸。

• 所有活着的僵尸向前走一步，也即从 $(x, y)$ 移动到 $(x, y-1)$ 。

任意时候，当某个僵尸与房屋的距离为 $0$（即，坐标为 $(0,0)$ 或 $(1,0)$），那么主角的脑子就会被吃掉，玩家输掉游戏。

如果到所有僵尸都被消灭的时候，上述事件仍末发生，则玩家胜利。

你被邀请来设计这个游戏的 AI。你并不在意玩家的游戏体验和游戏公司的收入，你只想让玩家尽可能地多受苦。因此：你想知道：

• 是否存在一种策略使得玩家一定失败。
• 如果存在，AI 在第一回合有多少种不同的行动策略使得玩家必败。

定义两种策略是不同的，当且仅当存在一个编号 $i$，使得僵尸 $i$ 在两种方案里不在同一个位置。 答案请对 $10^{9}+7$ 取模。

输入格式

第一行一个整数 $T$，表示数据组数。

每组数据包含两行，第一行一个整数 $N$，第二行 $N$ 个整数，第 $i$ 个数表示 $a_i$ 。

输出格式

对每组数据，输出一行一个整数，表示答案。

样例

3
2
1 1
3
1 2 3
4
1 1 1 1

2
0
14

第一组数据，把第一个僵尸或是第二个僵尸移动到第二行是两种不同的必胜方法。

第二组数据，不存在必胜策略。

第三组数据，只要不把所有僵尸放在同一行即可确保胜利，故方案数为 $2^{4}-2=14$。

限制与约定

对全部的测试数据， $1\le T \leq 20$，$1\le N \leq 2000$。

• 对于 $10$ 分的数据，$N \leq 8$。
• 对于另外 $20$ 分的数据，$N \leq 17$。
• 对于另外 $20$ 分的数据，$N \leq 100$，$a_{i} \leq 20$。
• 对于另外 $20$ 分的数据， $a_{i}$ 只有两种不同的取值。
• 对于另外 $30$ 分的数据，无特殊限制。

$\color{white}{\text{良心的出题人保证了}a_i\le 9}$