Mountain Problem

A mountain range has the property that among its N elements there is an index M inside the range 1 < M < N, for which the sequence formed by the first M elements (a₁, a₂, …, a_M) is ascending and nonconstant, and the sequence consisting of the last N – M + 1 elements (a_M, a_M + 1, …, a_N) is descending and nonconstant.

For example, the following 8 elements form a mountain range: {1, 1, 1, 2, 2, 2, 2, 1}.

These sequences with N elements are indexed from 1 to N, the elements being a₁, a₂, …, a_N. These are signed 32-bit integers, not necessarily distinct.

We can apply two types of symmetric swap operations on these elements:

1. swap(P, N – P + 1): swap the elements on the positions P and N – P + 1, placed equidistantly from the two ends of the sequence (P ≠ N – P + 1, 1 ≤ P ≤ N);
2. double_swap(P, Q, N – P + 1, N – Q + 1): swap simultaneously two pairs of elements. The elements from positions P and Q will be swapped simultaneously with the elements from positions N – P + 1 and N – Q + 1. The operation can be applied only if all four positions are distinct (P ≠ Q, P ≠ N – P + 1, Q ≠ N – Q + 1, Q ≠ N – P + 1, 1 ≤ P ≤ N, 1 ≤ Q ≤ N).

How many distinct mountain ranges can be achieved using any number of operations defined above?

Example 1

For N = 7 and a = {3,6,2,10,1,9,8}, we can obtain 4 distinct mountain ranges:

The first mountain range can be obtained from the sequence {3,6,2,10,1,9,8} with the following operations:

1. double_swap(1,5,7,3): the highlighted elements of {3,6,2,10,1,9,8} are swapped, and the mountain range of {1,6,8,10,3,9,2} is obtained;
2. double_swap(2,5,6,3): the highlighted elements of {1,6,8,10,3,9,2} are swapped, and the mountain range of {1,3,9,10,6,8,2} is obtained;
3. swap(3,5): the highlighted elements of {1,3,9,10,6,8,2} are swapped, and the mountain range of {1,3,6,10,9,8,2} is obtained.

The second mountain range obtained from {3,6,2,10,1,9,8} is:

1. double_swap(1,3,7,5): the range of {2,6,3,10,8,9,1} is obtained;
2. double_swap(2,3,6,5): the mountain range of {2,3,6,10,9,8,1} is obtained.

The third mountain range obtained from {3,6,2,10,1,9,8} is:

1. double_swap(2,5,6,3): the range of {3,1,9,10,6,2,8} is obtained;
2. double_swap(2,1,6,7): the range of {1,3,9,10,6,8,2} is obtained;
3. swap(2,6) to get the mountain range of {1,8,9,10,6,3,2}.

The fourth mountain range obtained from {3,6,2,10,1,9,8} is:

1. double_swap(7,2,1,6): the range of {9,8,2,10,1,3,6} is obtained;
2. double_swap(5,7,3,1) to get the mountain range of {2,8,9,10,6,3,1}.

Example 2

For N = 8 and a = {2,1,2,1,1,1,2,2}, with the help of swap and double_swap operations, we can get 2 distinct mountain ranges: {1,1,1,2,2,2,2,1} and {1,2,2,2,2,1,1,1}, respectively.

Input Specification

The input contains several sets of tests. Each test contains on its first line a number N, representing the length of the sequence (3 ≤ N ≤ 2005), and on the next line N natural numbers a_i, the elements of the mountain range (0 ≤ a_i ≤ 2 000 000 000), separated by a space.

Output Specification

Print as many lines as there are sets of tests in the input. Each line should contain the results corresponding to the data in the input in the order in which they are read. For each read string, print the number of distinct mountain ranges that can be obtained by applying the swap and double_swap operations on the elements of the given ranges. As this value can be very high, the result should be printed in modulo 111 181 111.

Note that each test case has at least one solution.

Sample Input

1. 8
2. 2 1 2 1 1 1 2 2
3. 7
4. 3 6 2 10 1 9 8
5. 3
6. 1 2 1
7. 9
8. 1 1 2 2 1 1 1 100 1

download as text file

Output for Sample Input

1. 2
2. 4
3. 1
4. 10

download as text file

Explanation

For the first test case, there are two solutions: {1,1,1,2,2,2,2,1} and {1,2,2,2,2,1,1,1}.

For the second test case, there are four solutions: {2,3,6,10,9,8,1}, {2,8,9,10,6,3,1}, {1,8,9,10,6,3,2}, and {1,3,6,10,9,8,2}.

For the third test case, there is only one solution: {1,2,1}.

For the fourth test case, there are ten solutions: {1,1,1,1,1,1,2,100,2}, {1,1,1,1,1,1,100,2,2}, {1,1,1,1,1,2,2,100,1}, {1,1,1,1,1,2,100,2,1}, {1,1,1,1,1,100,2,2,1}, {1,2,2,100,1,1,1,1,1}, {1,2,100,2,1,1,1,1,1}, {1,100,2,2,1,1,1,1,1}, {2,2,100,1,1,1,1,1,1}, and {2,100,2,1,1,1,1,1,1}.