Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

There is a permutation $a$ of size $n$, which satisfies $a_1=1$ and for each $i$ where $2\le i\le n$, $|a_i-a_{i-1}|\le2$.

Given $n$, find the number of possible such permutations.

Since the output may be extremely large, the answer should be taken modulo $10^9+7$.

Input Format

The input consists of a single line containing a positive integer $n\ (1 \le n \le 10^{18})$.

Output Format

Output the number of possible permutations.

Samples

4

4

32132

876675871

Sample 1 Explanation

The permutations are $(1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2)$.