Akash , the director of the famous Timus Coaching Institute was very happy after the results of the Entrance Examination, and decided to distribute sweets to the students according to their test scores. He shall distribute sweets according to the following conditions:

1. Every student must get at least one sweet.
2. A student with higher score gets more number of sweets than all students who scored less than him.

Help Akash to find out the minimum number of sweets that need to be distributed. Since the answer can be very large output it modulo 10⁹ + 7.

Input

The input consists of 3 lines. The first line contains T (1<=T<=10) denoting the number of test cases. The second line consists of a single integer N (1 <= N <= 10⁵) denoting the number of students.

The next line consists of N space separated integers a₁, a₂, a₃ ... a_n where a_i denotes the test score of the i^th student (0 <= a_i <= 10⁹).

Output

Output a single integer denoting the minimum number of sweets to be distributed by Akash.

Example

Input:
2
2
1 2
3
100 200 50

Output:
3
6