链接: https://cses.fi/problemset/task/1075

板块: Counting Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

如果 $1,2,\ldots,n$ 的一个排列中不存在相邻元素之差为 $1$，则称其为美丽的。

给定 $n$，你的任务是统计美丽排列的数量。

输入

唯一的一行输入包含一个整数 $n$。

输出

输出 $1,2,\ldots,n$ 的美丽排列数量，对 $10^9+7$ 取模。

数据范围

$1 \le n \le 1000$

样例输入

5

样例输出

14