#CS1075. 排列 II

排列 II

题目背景

翻译自 CSES-1075 题。

题目描述

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

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

输入格式

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

输出格式

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

样例

5

14

说明/提示

$1 \leq n \leq 10$