SK_001 - Rightful Distribution


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 109 + 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 <= 105) denoting the number of students.

The next line consists of N space separated integers a1, a2, a3 ... an where ai denotes the test score of the ith student (0 <= ai <= 109).

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

hide comments
akhilkumar31e: 2020-04-22 14:51:37

Cake walk...;)

vinay1998: 2019-08-25 17:44:01

Mind the mod (10^9)+7, cost me 1 WA. Pretty straight forward other than that.

Last edit: 2019-08-25 17:44:51

Added by:suraj1611
Date:2019-05-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All