题目描述

给定一个 n，请你构造一个长度为 n 的排列 $p_1,p_2,...,p_n$，使得该排列中不存在对于任意的三个参数 i,j,k，满足 i<j<k、且 $p_i<p_j<p_k$​。

请问对于给定的参数 n，有多少个长度为 n 的排列满足以上条件。由于答案可能较大，输出对$10^9+7$ 取模的结果即可。

输入格式

输入共一行，一个正整数n。

输出格式

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

样例

3

5

提示

样例说明

1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 都可。 只有 1,2,3 不满足条件

数据范围

• 对于 30% 的数据，$1≤n≤10$
• 对于 60% 的数据，$1≤n≤100$
• 对于 100% 的数据，$1≤n≤10^4$