问题描述

有 $n$ 家公司排成一排，其中第 $i$ 家公司的工资为 $a_i$，这些公司的工资是一个排列，即 $1 \sim n$ 这些数字各出现一次。现在假设每家公司中都有一名想要跳槽的员工，员工跳槽时只会向工资更高的公司跳槽。对于员工而言，他们深知自己的工资不可能一步登天，只能慢慢提升，所以他们的跳槽方式是这样的：

从当前公司往左和右找第一家比自己工资更高的公司进行跳槽，如果左右各有一家公司比自己的工资高，则选择工资较低的公司跳槽。员工会一直重复上述操作，直到跳到工资最高的公司。

例如有 5 家公司，工资分别是 4 1 2 3 5。

那么处在第三家公司的员工（他此时工资为 2），他会进行三次跳槽，工资分别是 [3, 4, 5]。

当公司工资的排列确定后，每名员工跳槽的轨迹就是确定的，但他们开始跳槽的时间不确定。也就是说如果如果两名员工的跳槽轨迹中都有公司 A，则说明他们可能在 A 公司相遇。

我们定义 $l[i],r[i]$ 为当前到达公司 $i$ ，且来自第 $i$ 家公司左边、右边的跳槽次数最多的员工的跳槽次数（如果不存在，则为 0）。

例如排列 4 1 2 3 5，他们的 $l,r$ 数组分别是：

$l:0,0,1,2,4$ , $r:3,0,0,0,0$

现在要求对于所有的位置 $i$，都有 $|l[i]-r[i]| \leq 1$，请问有多少种工资的排列能够满足要求？由于答案可能很大，请输出答案对 $10^9+7$ 取模的结果。

输入格式

一个数字$N$，表示公司个数。

输出格式

输出一个数字，表示方案数 mod $10^9+7$。

3

2

样例解释

当 $N=3$ 时，排列 [1,3,2],[2,3,1] 合法，其他都不合法。

104

624737290

数据范围

对于30%的数据：$N\leq 10$。

对于60%的数据：$N\leq 100$。

对于80%的数据：$N\leq 1000$。

对于100%的数据：$N\leq 5000$。

大样例

T4sample