题目描述

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

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

输入格式

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

输出格式

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

数据范围

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

样例数据

输入:

2

输出:

3

输入:

8

输出:

153