← 返回比赛

已结束 ZZSR普及赛#2

← 上一题下一题 →

A7337 | $拆卸爆能器$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小W（并非上题那个 小W）要拆卸爆能器，可是这个爆能器被做了手脚，需要输入密码才能拆卸。 有如下两种类型的拼图（如果您看不清可以放大）： 问你用这两种拼图覆盖一个 $2\times n$ 的矩形的方案数，答案对 $10^9+7$ 取模。 拼图可以在此基础上任意旋转，但不能拆卸或斜放，或者超出规定的矩形。 总方案数就是密码，小W 需要你的帮助。

输入格式

第一行输入一个正整数 $T$ 代表数据组数。 接下来 $T$ 行，每行一个正整数 $n$，含义如题。

输出格式

本题一个测试点内有多组测试数据。 对于每组测试数据，输出一行一个整数表示总方案数，记得取模 $10^9+7$。

输入输出样例

输入 #1

输出 #1

样例解释 对于第 $2$ 组测试数据，以下是五种方案： 数据范围 对于 $100\%$ 的数据，$1\le T \le 10$。 测试点编号$n\le$$1\sim 2$$10^3$$3\sim 5$$10^6$$6\sim 10$$10^{12}$ 温馨提示 样例较强，如果您打的是第一档的暴力可以删除后两组样例；如果您打的是第二档暴力可以删除最后一组样例；如果您通过了样例，那您大概率可以通过此题。

C++ 编辑器

输入

输出