H. marble的神秘数列

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

在二次元的奇幻世界中,隐藏着一个神秘的数列,它似乎拥有某种特殊的魔力。这个数列的前三项均为1,而之后的每一项都遵循着一个独特的规律。具体来说,对于数列的第项(大于等于4),它满足以下公式:

在二次元世界中,有一个特别的日子——3月26日,它与这个数列似乎有着某种神秘的联系。传说在这一天,数列中的某一特定项将揭示出一个深藏的奥秘。

现在,marble——一位热爱二次元的探险家,决心揭开这个秘密。请你帮助marble编写一个程序,输入一个正整数大于等于4),输出数列的第项的值,由于这个数列很大请对1000000007取模

输入格式

多组询问,第一行输入一个整数t代表询问数,后面行每行一个整数表示询问数列的第几项

输出格式

行每行一个整数表示答案

样例

样例输入

2
4
11

样例输出

11
139801

数据范围与提示