题目描述

给定一个 $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

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

数据范围

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