Bạn được cho số \(n\) và một dãy \(a\) gồm \(n\) phần tử \((3 ≤ n ≤ 10^6; a_i ≤ 10^9\) với \(1 ≤ i ≤ n)\) Biết rằng \(a_i ≠ a_j\) với mọi \(1 ≤ i, j ≤ n\)

Hãy đếm số dãy thỏa mãn chia lấy dư \(10^9 + 7\): không tồn tại bộ ba số \((i, j, k)\) sao cho \(1 ≤ i < j < k ≤ n\) và \(a_k < a_i < a_j\)

Input

Dòng đầu tiên gồm số \(t\) \((t ≤ 10^4)\), chỉ số test cases của bài. Biết rằng tổng \(n\) của \(t\) test cases tối đa bằng \(10^6\)

Dòng đầu tiên của mỗi test cases gồm số \(n\) \((3 ≤ n ≤ 10^6)\), chỉ độ dài của dãy \(a\)

Dòng thứ hai của mỗi test cases dãy \(a\) \((a_i ≤ 10^9\) với \(1 ≤ i ≤ n)\)

Output

Gồm \(t\) dòng, mỗi dòng gồm 1 số là số cách sắp xếp dãy thỏa mãn chia lấy dư \(10^9 + 7\)

Example

1
3
2 7 4

5