题目描述

给定一个 $1\sim n$ 的排列 $a$。

对于一个 $1\sim n$ 的排列 $b$，定义权值 $f(b)$ 为：最少进行多少次如下操作，才能把 $a$ 变成 $b$：

• 交换两个位置相邻但值不相邻的元素，即若当前排列中相邻两个元素为 $x,y$，只有当 $|x-y|\ge 2$ 时，才允许交换它们。

特别地，若不可能把 $a$ 变成 $b$，则定义 $f(b):=0$。

请计算所有排列 $b$ 的 $f(b)$ 之和，并对 $10^9+7$ 取模。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数，表示排列 $a_1,a_2,\dots,a_n$。

输出格式

输出一行一个整数，表示答案。

样例 1 输入

4
3 1 2 4

样例 1 输出

6

样例 2 输入

4
1 2 3 4

样例 2 输出

0

样例 3 输入

9
1 9 2 6 8 7 5 4 3

样例 3 输出

7206

数据范围与约定