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$.
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$
One line two number indicating the length of the longest BoBo sequence and the quantity of them.
answer mod 10^9+7