对于一个数组 $a = [a_1, a_2, \dots, a_n]$，$n \ge 2$，其差分数组定义为 $[a_2 - a_1, a_3 - a_2, \dots, a_n - a_{n-1}]$。 如果数组 $a = [a_1, a_2, \dots, a_n]$ 反转后保持不变，则称其为回文数组。 数组 $a$ 的一个排列是指一个与 $a$ 包含相同元素，但顺序可能不同的数组。 给定一个长度为 $n$ 的数组 $a$。求 $a$ 的所有不同排列中，差分数组为回文数组的排列数量。两个长度相同的数组 $a$ 和 $b$ 被认为是不同的，当且仅当存在某个 $i$ 使得 $a_i \neq b_i$。 由于该数字可能非常大，请输出其对 $10^9 + 9$ 取模的结果。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。 接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 5 \cdot 10^5$)，表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)。 保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，在单独的一行中输出一个数字，即该测试用例的答案对 $10^9 + 9$ 取模的结果。

样例

输入 1

5
3
2 3 1
4
1 1 1 1
3
1 2 4
7
0 200 0 200 50 100 150
14
-1 0 1 2 3 4 5 6 7 8 9 10 11 12

输出 1

2
1
0
24
645120

说明

在第一个测试用例中，数组 $[2, 3, 1]$ 有六个排列：$[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]$。它们的差分数组分别为 $[1, 1], [2, -1], [-1, 2], [1, -2], [-2, 1], [-1, -1]$。其中只有两个是回文的：$[1, 1]$ 和 $[-1, -1]$。因此，只有两个排列的差分数组是回文的，即 $[1, 2, 3]$ 和 $[3, 2, 1]$。

在第二个测试用例中，只有一个排列 $[1, 1, 1, 1]$。它的差分数组 $[0, 0, 0]$ 是一个回文数组。

在第三个测试用例中，没有任何排列的差分数组是回文的。