1859 - 三排地砖
Description

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

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


Input

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

Output

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

Examples

Input

2

Output

3

Input

8

Output

153
Hint

对于 30\% 的数据,1\leq n\leq 16

对于 70\% 的数据,1\leq n\leq 300

对于 100\%的数据,1\leq n\leq 200000


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 12
通过次数 9