Description

设序列\({x_1,x_2,x_3,x_4}\)是某序列\(a_i\) (i=1,2,3…,N) 的一个子序列。

我们称序列\(x_i\)是有效的当且仅当\(x_1 \lt x_2 \lt x_4 \lt x_3\)成立

现保证序列\(a_i\)是是\(1\)~\(n\)的一个排列，请你求出所有可能的序列\(x_i\)的数量。

因为答案可能很大，请输出答案mod \(10^9+7\)之后的结果

Format

Input

第一行包含一个正整数 \(n\) ，接下来一行包含 \(n\) 个正整数，\(x_i\) (i=1,2,3…,N) ，表示序列的第 \(i\) 个元素。保证 \(x_1\) , \(x_2\) ,…, \(x_n\) 是\(1\)~\(n\)的一个排列。

Output

仅包含一个数，表示答案对\(10^9+7\)的余数。

Sample 1

Input

5

1 5 3 2 4

Output

0

Sample 2

Input

4
1 2 4 3

Output

1

Limitation

0.2s, 16MB for each test case.

1.\(n \leq 600\)

2.\(n \leq 2000\)

3.\(n \leq 4000\)

4.\(n \leq 5000\)

5-10. \(n \leq 200000\)

Hint

题目难度已下调,时限已放宽,have fun and enjoy yourself！