Get Number of Perfect Packaging

Each package gets a stamp numbered 1..5. When the price rises between adjacent packages the stamps must strictly increase, when it falls they must strictly decrease, and when it stays equal the stamp numbers must differ. Count the plans modulo 1000000007, and output 0 if there is none.

输入格式

The first line contains n; the second line contains the prices. 1≤n≤100000, 1≤price≤100000.

输出格式

Output a single integer, the answer.

样例 1

输入：

3
3 1 1

输出：

40

样例 2

输入：

3
1 2 3

输出：

10

样例 3

输入：

6
1 2 3 4 5 6

输出：

0

样例说明

The answers are 40, 10 and 0. Six strictly increasing prices need six different stamps, but there are only five.