Bohdana is repainting a fence made of planks, numbered from to from left to right. Plank currently has colour c_i. Colours are positive integers, and several planks may share a colour.
The paint on the fence is still wet, so Bohdana repaints it with strokes. In one stroke she chooses two planks and with 1 \le l \le r \le n, picks up the current colour of plank on a dry brush, and drags the brush to the right up to plank . After the stroke, all planks l, l+1, \ldots, r have the colour that plank had just before the stroke, and the other planks do not change.
Bohdana may make any number of strokes, possibly none, one after another. How many different colourings of the fence can she obtain? Two colourings are different if at least one plank has different colours in them. The initial colouring is counted too.
Since the answer can be very large, print it modulo .
The first line contains a single integer (1 \le t \le 5000) — the number of test cases.
Each test case consists of two lines. The first line contains an integer (1 \le n \le 5000) — the number of planks. The second line contains integers c_1, c_2, \ldots, c_n (1 \le c_i \le 10^9) — the colours of the planks from left to right.
The sum of over all test cases does not exceed .
For each test case print one integer — the number of different colourings Bohdana can obtain, modulo .
Example 1
In the first test case the fence is (1, 2, 3), and the possible colourings are (1, 2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 2) and (1, 1, 1). For example, (1, 1, 2) is obtained by the stroke l = 2, r = 3, which gives (1, 2, 2), followed by the stroke l = 1, r = 2. The colouring (1, 3, 2) cannot be obtained. The figure shows these two strokes: the arrow above the fence is the path of the brush.
In the second test case the possible colourings are (5, 7, 5, 7), (5, 7, 5, 5), (5, 7, 7, 5), (5, 7, 7, 7), (5, 5, 7, 5), (5, 5, 7, 7), (5, 5, 5, 7) and (5, 5, 5, 5). For example, (5, 7, 7, 5) is obtained by the stroke l = 3, r = 4 followed by the stroke l = 2, r = 3.
In the third test case all planks already have the same colour, and no stroke changes anything.