题目背景

翻译自 CSES-1075 题。

题目描述

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

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

输入格式

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

输出格式

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

样例

5

14

数据范围

• $1 \le n \le 1000$