Problem Description

There is an array with $n$ elements named $a$.If $seq$ is a palindrome subsequence of $a$,whose elements are increasing from the middle to both ends,then we call it a BoBo sequence.

Two BoBo sequence are considered different if and only if they have different length or there is at least one position has a different number.

Your task is to calculate how many different longest BoBo sequence are there in $a$.

Input

There are several test cases.

The first line contains an integer $n$.

The second contains $n$ numbers indicating $a_i$.

$1\leq n\leq 5000,1\leq a_i\leq 20000$

Output

One line two number indicating the length of the longest BoBo sequence and the quantity of them.

answer mod 10^9+7

5
1 1 1 1 1 
5
2 2 3 2 2

5 1
4 1

Author

绍兴一中