题目描述

33DAI 有一块 $3 \times n$ 的棋盘，他想用 $1 \times 2$ 的多米诺骨牌把它完全铺满：每块骨牌恰好盖住两个相邻的格子，每个格子恰好被一块骨牌盖住，骨牌不能重叠也不能超出棋盘。

记 $f(n)$ 为 $3 \times n$ 棋盘的铺法数（$f(n)$ 可能很大，下面各问都要求对 $10^9 + 7$ 取模）。

33DAI 想让你写一个程序：给出题号，就输出那道小题的答案。他准备了 $10$ 道小题：

1. $n = 2$，求 $f(n) \bmod (10^9+7)$。
2. $n = 4$，求 $f(n) \bmod (10^9+7)$。
3. $n = 10$，求 $f(n) \bmod (10^9+7)$。
4. $n = 100$，求 $f(n) \bmod (10^9+7)$。
5. $n = 1000$，求 $f(n) \bmod (10^9+7)$。
6. $n = 10^6$，求 $f(n) \bmod (10^9+7)$。
7. $n = 10^9$，求 $f(n) \bmod (10^9+7)$。
8. $n = 10^{12}$，求 $f(n) \bmod (10^9+7)$。
9. $n = 10^{18}$，求 $f(n) \bmod (10^9+7)$。
10. 求 $f(2) + f(4) + f(6) + \dots + f(20)$ 的值（这些项都很小，不必取模，直接输出它们的和）。

输入格式

从标准输入读入数据。

一行一个整数 $T$（$1 \le T \le 10$），表示要问第 $T$ 道小题。

输出格式

输出到标准输出。

一行，第 $T$ 道小题的答案（一个非负整数）。

样例

样例 1 输入

2

样例 1 输出

11

样例 2 输入

9

样例 2 输出

558008386

样例解释

• 样例 1 问的是第 2 问：$n = 4$ 时，$3 \times 4$ 的棋盘共有 $11$ 种铺法，所以输出 11。
• 样例 2 问的是第 9 问：$3 \times 10^{18}$ 的铺法数很大，对 $10^9+7$ 取模后是 $558008386$，所以输出 558008386。

提示

• 本题是提交答案题：不需要读入数据本身，只要按题号输出对应那一问的答案即可。
• 输出必须恰好一行，行尾可以有一个换行；不要输出多余的空格、空行或说明文字。
• 更靠后的小问 $n$ 更大，逐项递推会超时，需要考虑更快的做法。

数据范围

对于所有测试数据，保证 $1 \le T \le 10$。

一共 $10$ 个测试点（一道小问一个测试点），每个测试点 $10$ 分，按测试点计分。