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.

Background

众所周知，心灵终结是一个深受玩家喜爱的《命令与征服：红色警戒2 尤里的复仇》的扩展模组，以其剧情丰富和战役任务众多而闻名。这个MOD不仅提供了一个全新的故事线，从《红色警戒1》的结局开始，发展出一个与原版尤里的复仇截然不同的世界观，而且还增加了一个全新的阵营——焚风反抗军，使得游戏的对战平衡性得到了极大的提升。玩家可以在盟军、苏联、尤里以及焚风四个阵营中选择，体验各自独特的科技、战术和武器。心灵终结的战役任务数量超过一百三十个，每个任务都精心设计，为玩家提供了深度的游戏体验。此外，MOD还提供了大量的遭遇战地图和多人游戏模式，使得无论是单人战役还是在线对战，都能享受到平衡且充满挑战的游戏乐趣。

众所周知，纵火狂是拉丁同盟专属的伪装型步兵，以其独特的潜入和破坏能力在《红色警戒2》MOD心灵终结中占有一席之地。纵火狂不同于一般的间谍单位，他们的主要任务是潜入敌军基地，使用不触发警报的纵火技巧，悄无声息地将敌人的基地烧毁。他结合了疯狂伊文的凶恶与破坏者的谨慎，拥有与破坏者和盟军间谍相同的伪装能力，能够轻易越过敌军防线，并在敌军建筑上放火。这种火焰能够有效破坏那些没有得到足够保护的基地，因为只要纵火狂安置好火种，他就可以确保至少烧毁一两个建筑。值得注意的是，纵火狂在布置火种时并不会失去他的伪装能力，但工程师可以在火种引燃前解除它 。纵火狂的这种能力使他成为了拉丁同盟部队中以安静而又意想不到的方式破坏建筑的大师。

Description

现在纵火狂在要往焚风反抗军的重工里面放一把火，想要进入重工内部，需要通过一个铁骑兵的盘问。 那个铁骑兵问道: 一个01串$S$被认为是优美的，那么这个字符串满足下面两个条件

• s是回文的
• s中1的数量为奇数

现在问你有多少长度为n的01串是优美的？

由于纵火狂并不擅长解决这类问题，你能帮帮他吗？ 请你输出答案模1e9+7之后的结果。

Format

Input

第一行一个$t(1\le t \le 1e5)$表示有t组数据。 接下来t行每行一个整数$n(1\le n \le 1e9)$

Output

对于每组数据，输出一行答案。对1e9+7取模

Samples

1
3

2

Hints

Need a light? Burn, baby, BURN!! Set them ablaze! I’ll live again!