B. API Request
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

A permutation $$$p$$$ of length $$$n$$$ is called good if for each $$$i$$$ from $$$1$$$ to $$$n$$$ the following condition holds:

  • Let $$$x$$$ be the number of indices $$$j$$$ such that $$$i \lt j \le n$$$ and $$$p_i \lt p_j$$$, $$$x$$$ must be a multiple of $$$a_{p_i}$$$.

Find the number of good permutations modulo $$$10^9 + 7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t (1 \le t \le 5 \cdot 10 ^ 4)$$$. The description of the test cases follows.

The first line of each test case contains the integer $$$n (1 \le n \le 3 \cdot 10 ^ 5)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n (1 \le a_i \le n)$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output one integer: the answer modulo $$$10 ^ 9 + 7$$$.

Example
Input
3
3
1 1 1
3
1 2 3
5
2 1 2 1 2
Output
6
3
48
Note

In the third test case the permutation $$$[3, 2, 1, 4, 5]$$$ is good because :

  • for $$$i = 1$$$, there are two indices $$$j$$$ such that $$$i \lt j \le n$$$ and $$$p_i \lt p_j$$$, which are $$$4$$$ and $$$5$$$, and the condition holds because 2 is a multiple of $$$a_{p_i} = a_3 = 2$$$.
  • for $$$i = 2$$$, there are two indices $$$j$$$ such that $$$i \lt j \le n$$$ and $$$p_i \lt p_j$$$, which are $$$4$$$ and $$$5$$$, and the condition holds because 2 is a multiple of $$$a_{p_i} = a_2 = 1$$$.
  • for $$$i = 3$$$, there are two indices $$$j$$$ such that $$$i \lt j \le n$$$ and $$$p_i \lt p_j$$$, which are $$$4$$$ and $$$5$$$, and the condition holds because 2 is a multiple of $$$a_{p_i} = a_1 = 2$$$.
  • for $$$i = 4$$$, there is one index $$$j$$$ such that $$$i \lt j \le n$$$ and $$$p_i \lt p_j$$$, which is $$$5$$$, and the condition holds because 1 is a multiple of $$$a_{p_i} = a_4 = 1$$$.
  • for $$$i = 5$$$, there are no indices $$$j$$$ such that $$$i \lt j \le n$$$ and $$$p_i \lt p_j$$$, and the condition holds because 0 is a multiple of $$$a_{p_i} = a_5 = 2$$$.