该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

1~n n个数字从小到大排成一排：[1,2,3,..,n]。现在我们要对这些数字重新排列，重新排列后的数列要满足以下限制：
（1）仍旧是1~n的一个合法排列（即每个数字恰好出现一次）
（2）对于每个数字num来说，它在新数列中的下标我们称为“新位置”，它在原数列中的下标我们称为“原位置”（显然数字num的原位置就是num）。要求每个数字的“新位置”与“原位置”的差的绝对值不超过1
现在输入一个数字n，你要求解出有多少种重新排列后的数列满足以上限制。注意，每个数字位置都不改变也是一种特殊的方案。
换句话说，设a[1]...a[n]是1~n的一个排列，那么其必须满足|ai-i|<=1，你需要求出给定n情况下，a的数目
最后结果可能很大，所以输出结果对1e9+7取模。

Format

Input

输入一个整数n(1<=n<=1000000)

Output

输出一个整数ans，表示满足题意的数列个数。答案对1e9+7取模

Sample 1

Input

4

Output

5

Limitation

1s 256MB

Hint

n=4时，以下5种数列是满足限制的：
[1,2,3,4]
[1,2,4,3]
[1,3,2,4]
[2,1,3,4]
[2,1,4,3]