Randal 是高维空间的大师。他将生活在他空间里的所有物种都视为萤火虫。有一天，他想出了一个问题，但没能解决它。你能解决这个问题吗？

有一个 $n$ 维超立方体子空间，他想用最少数量的萤火虫将其覆盖。该空间的边长为 $p_1, p_2, \dots, p_n$，这意味着该空间可以由 $\prod_{i=1}^n p_i$ 个超立方体单元组成。

如果某个单元有萤火虫访问过，则认为该单元被覆盖。每只萤火虫可以通过自身的移动覆盖多个单元。假设一只萤火虫位于坐标 $(x_1, x_2, \dots, x_n)$，其中 $1 \le x_i \le p_i$ ($i = 1, 2, \dots, n$)，如果满足 $1 \le x_i \le y_i \le p_i$ ($i = 1, 2, \dots, n$) 且 $\sum_{i=1}^n |x_i - y_i| = 1$，它就可以移动到另一个坐标 $(y_1, y_2, \dots, y_n)$。此外，一只萤火虫的旅程可以在任何位置开始或结束，并且可以进行任意次数的移动，但每只萤火虫只能旅行一次。

你的任务是确定所需的最少萤火虫数量，并将答案对 $(10^9 + 7)$ 取模后输出。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

接下来的行描述了所有测试用例。对于每个测试用例： 第一行包含一个整数 $n$，表示空间的维度。 第二行包含 $n$ 个空格分隔的整数，表示空间的边长。

$1 \le T \le 2000, 1 \le n \le 32, 1 \le p_i \le 10^9$ ($i = 1, 2, \dots, n$)。 保证满足 $n > 8$ 的测试用例不超过 200 个，满足 $n > 16$ 的不超过 20 个，满足 $n > 24$ 的不超过 2 个。

输出格式

对于每个测试用例，输出一行，包含答案对 $(10^9 + 7)$ 取模后的结果。

样例

样例输入 1

3
1
10
2
3 4
3
3 3 3

样例输出 1

1
3
7

说明

对于第一个样例，一只萤火虫可以覆盖所有单元。

对于第二个样例，一种可能的最佳方式是每只萤火虫覆盖所有具有相同第二个坐标的单元，这需要三只萤火虫。