2026年4月算法设计模拟题

A
B
C
D
E

C. 三排地砖 T3

Description

有一条道路需要铺设地砖，这条道路由 $n\times 3$ 个方格组成。只有一种规格的地砖，大小是 $1\times2$ 规格的，也就是恰好可以覆盖两个方格。请计算有多少种方法，将这条道路铺满地砖。

由于方案数可能很大，输出它模 $1,000,000,007$ 的余数即可。

Input

单个整数：表示 $n$ 。(保证 $n$ 为偶数)

Output

单个整数：表示方案数模 $1,000,000,007$ 的余数。

Examples

Input

Output

Input

Output

Hint

数据范围

对于 $30\%$ 的数据， $1\leq n\leq 16$ ；
对于 $70\%$ 的数据， $1\leq n\leq 300$ ；
对于 $100\%$ 的数据， $1\leq n\leq 200000$ 。

Submit

Login

Time Limit	1 second
Memory Limit	128 MB

Submit