For an array $$$a=[a_1, a_2, \dots, a_n]$$$, $$$n \ge 2$$$, its difference array is defined as $$$[a_2-a_1, a_3 -a_2, \dots, a_n-a_{n-1}]$$$.
The array $$$a=[a_1, a_2, \dots, a_n]$$$ is a palindrome if it doesn't change after being reversed.
A permutation of array $$$a$$$ is an array which has the same elements as $$$a$$$, but possibly in a different order.
You are given an array $$$a$$$ of length $$$n$$$. Find the number of distinct permutations of $$$a$$$ whose difference array is a palindrome. Two arrays $$$a$$$ and $$$b$$$ of same length are distinct if and only if for some $$$i$$$, $$$a_i \ne b_i$$$.
As this number can be very large, print it modulo $$$10^9+9$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
For each test case, print a single number on a separate line — the answer to the test case modulo $$$10^9+9$$$.
532 3 141 1 1 131 2 470 200 0 200 50 100 15014-1 0 1 2 3 4 5 6 7 8 9 10 11 12
2 1 0 24 645120
In the first test case, the array $$$[2,3,1]$$$ has six permutations: $$$[1,2,3]$$$, $$$[1,3,2]$$$, $$$[2,1,3]$$$, $$$[2,3,1]$$$, $$$[3,1,2]$$$, $$$[3,2,1]$$$. Their difference arrays are $$$[1,1]$$$, $$$[2,-1]$$$, $$$[-1,2]$$$, $$$[1,-2]$$$, $$$[-2,1]$$$, $$$[-1,-1]$$$. Of them only two are palindromes: $$$[1,1], [-1,-1]$$$. So, the only two permutations with palindromic difference arrays are $$$[1,2,3]$$$ and $$$[3,2,1]$$$.
In the second test case, there is only one permutation $$$[1,1,1,1]$$$. Its difference array $$$[0,0,0]$$$ is a palindrome.
In the third test case, none of permutations has a palindromic difference array.
