You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

上一个画图游戏 题目详情 - 画图游戏 - ACjudge

题目描述

给你一个 $3 \times n$ 的矩阵, 要求你用 $1 \times 2$ 的木棍将矩阵中所有的方格覆盖, 一共有多少不同的摆放方案?

注意, 方案数可能很大, 需要对 1000000007 求模.

输入格式

一个整数 $n$

输出格式

输出一个整数, 表示有多少摆放方案.

样例 #1

样例输入 #1

2

样例输出 #1

3

样例 #2

样例输入 #2

8

样例输出 #2

153

数据范围

• $0 \le n \le 10^{6}$
• 确保 $n$ 是偶数