木匠收到了一份制作木制指示牌的订单。每一块木板都必须与前一块木板垂直对齐，固定在上一块木板箭头基座的位置或其对侧，并用特制的螺丝固定。两块木板必须有重叠部分。

木匠记录了一个整数序列来编码设计师提供的草图，但该序列并不能唯一确定一个模型，而他已经丢弃了原始草图。这件看似琐碎的任务对他来说变成了一个巨大的拼图。

该序列（包含 $1 + N$ 个元素）编码了从指示牌底部到顶部的 $N$ 个箭头。第一个元素是底部箭头左侧的位置。其余 $N$ 个元素定义了从底部到顶部各箭头基座的位置：第 $i$ 个元素是第 $i$ 个箭头基座所在的位置。例如，图中描绘的两个指示牌都可以用 $2\ 6\ 5\ 1\ 4$ 来编码。

由于木板必须与前一块木板垂直对齐（对齐到前一个箭头的基座或其对侧），如果序列是 $2\ 6\ 5\ 1\ 4\ 3$，则第五个箭头（在图中所示的任何指示牌中）可以用螺丝固定在 $1$（指向右侧）或 $4$（指向左侧），而箭头基座位于 $3$。

如果序列是 $2\ 3\ 1$，则第二个箭头只能用螺丝固定在 $3$ 处并指向左侧，因为连续的木板必须重叠。

所有的箭头形状相似，设计师告诉木匠，它们的基座位于不同的垂直线上，底部箭头的左侧也是如此，它们共同构成了 $1 \dots (N+1)$ 的一个排列。这就是为什么木匠忽略了细节，只写下了这个排列（例如 $2\ 6\ 5\ 1\ 4\ 3$）。

任务

给定木匠写下的数字序列，计算可以制作出的不同指示牌的数量。由于该数字可能非常大，你必须将其对 $2^{31} - 1 = 2147483647$ 取模。序列中的第二个整数总是大于第一个整数（底部箭头总是指向右侧）。

输入格式

第一行包含一个整数 $N$，第二行包含一个 $1$ 到 $N+1$ 的整数排列。同一行中的整数由单个空格分隔。

数据范围

$1 \le N < 2000$ 箭头的数量。

输出格式

输出一行，包含可以由给定排列描述的不同指示牌的数量（对 $2^{31} - 1 = 2147483647$ 取模）。

样例

样例输入 1

5
2 6 5 1 4 3

样例输出 1

6

样例输入 2

2
2 3 1

样例输出 2

1

样例输入 3

20
3 21 10 15 6 9 2 5 20 13 17 19 14 7 11 18 16 12 1 8 4

样例输出 3

1887