#CS1075. 排列 II

排列 II

题目背景

翻译自 CSES-1075 题。

题目描述

一个由整数 $1, 2, \dots, n$ 组成的排列被称为“美丽的”，如果没有相邻的元素其差值为 1。

给定 n，你的任务是计算美丽排列的个数。

输入格式

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

输出格式

输出一个整数，表示排列 $1, 2, \dots, n$ 的美丽排列个数，结果需要对 $10^9 + 7$ 取模。

样例

5

14

说明/提示

$1 \leq n \leq 10$