题目描述

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

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

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

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

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

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

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

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

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

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

• 是否存在一种策略使得玩家一定失败。

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

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

输入格式

第一行一个整数 $\mathrm{T}$, 表示数据组数。 每组数据包含两行，第一行一个整数 $N$, 第二行 $\mathrm{N}$ 个整数, 第 $\mathrm{i}$ 个数表示 $\mathrm{a[i]}$ 。

输出格式

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

样例

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

2
0
14

样例解释

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

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

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

大数据

限制与约定

对全部的测试数据, $T \leq 20, N \leq 2000$.

• 10 分的数据, $N \leq 8$.

• 20 分的数据, $N \leq 17$.

• 20 分的数据, $N \leq 100, a_{i} \leq 20$.

• 20 分的数据， $a_{i}$ 只有两种不同的取值.

• 30 分的数据，无特殊限制.