## Another Contest 8 Problem 5 - U-Turn Finesse

View as PDF

Points: 15
Time limit: 0.5s
Memory limit: 64M

Problem type

Brandon likes sequences that go up and down. Given a list of integers, compute the number of subsequences that go up and down - that is to say, there is a unique maximal integer in the subsequence, and the prefix of the subsequence ending at that integer is strictly increasing, and the suffix of the subsequence starting at that integer is strictly decreasing. The subsequence must be nonempty.

Recall that a subsequence is obtained by deleting some (possibly zero) integers from the list. Two subsequences are distinct if and only if some integer is deleted in one subsequence but not the other.

#### Constraints   The sum of all in an input file will not exceed .

#### Input Specification

The first line contains a single positive integer , the number of test cases. test cases follow.

Each test case starts with a line containing a single positive integer, . The next line contains space-separated positive integers.

#### Output Specification

Output lines. On the th line, output the number of subsequences that go up and down, modulo , for the th test case.

#### Sample Input

2
3
1 3 2
4
1 3 2 4

#### Sample Output

7
13