Richard 喜欢区间和，Anita 喜欢回文串。

Richard 有一个包含 $n$ 个非负整数的数组 $a_1, a_2, \dots, a_n$。他想将其划分为若干个段，并计算每一段的区间和。

Anita 想知道有多少种划分方式，使得这些区间和的数字拼接在一起形成一个回文串。一个字符串是回文串，当且仅当它与其反转后的字符串相同。

例如，数组 $a = [1, 1, 4, 5, 1, 4, 1, 9, 1, 9]$ 可以划分为 3 个段 $[1, 1, 4, 5], [1, 4, 1, 9, 1], [9]$，这些段的和分别为 $11, 16, 9$，因此该划分产生的字符串为 $11169$。

注意，和始终不包含前导零。这意味着同一种划分只会产生唯一可能的字符串。

由于 Richard 的数组太大，Anita 无法计算出答案并为此哭泣。你能帮帮她吗？

由于答案可能非常大，你只需要输出答案对 $10^9 + 9$ 取模的结果。

输入格式

每个测试包含多个测试用例。

第一行包含一个整数 $t$ ($1 \le t \le 100$)。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 150$)，表示数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 666666$)。

保证所有测试用例的 $n$ 之和不超过 $200$。

输出格式

对于每个测试用例，输出一行一个整数，表示答案对 $10^9 + 9$ 取模的结果。

样例

输入 1

5
2
123456 654321
5
0 0 0 0 0
6
1 1 1 1 1 1
7
1 1 4 5 1 4 1
9
1 2 3 1 1 1 2 1 1

输出 1

2
16
8
4
6

说明

在第一个样例中，划分 $[123456], [654321]$ 得到 $123456654321$，划分 $[123456, 654321]$ 得到 $777777$，两者均为回文串。

在第二个样例中，任何划分都会产生一个仅包含零的字符串，显然是回文串。因此答案为 $2^4 = 16$。

在第三个样例中，有效的划分为： $[1], [1], [1], [1], [1], [1] \to 111111$ $[1], [1], [1, 1], [1], [1] \to 11211$ $[1], [1, 1], [1, 1], [1] \to 1221$ $[1], [1, 1, 1, 1], [1] \to 141$ $[1, 1], [1], [1], [1, 1] \to 2112$ $[1, 1], [1, 1], [1, 1] \to 222$ $[1, 1, 1], [1, 1, 1] \to 33$ $[1, 1, 1, 1, 1, 1] \to 6$