3725: Leo的简单规律题
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：3
题目描述
Leo喜欢吃烧烤，而且只吃三种，羊肉串，青菜，火腿肠，她吃烧烤之前喜欢把烧烤摆成一长串，而且还有特别的摆放规则，摆错了她这一顿就不吃了。
规则有：1.对于连续的三个烤串，不能三个烤串都是同一种。
2.对于连续的三个烤串，如果三种烤串都有，青菜不能放在中间（在吃肉中途吃菜是会令人自闭的）
3.依旧是对于连续的三个烤串，第一串和第三串都是青菜的话，中间不能是羊肉或者火腿肠（她的意思是吃素减肥）
现在有三种烤串都有无数根，她想摆出长度为n的烤串，请你求出方案数（由于结果可能会很大，所以只需给出答案模1000000007）
规则有：1.对于连续的三个烤串，不能三个烤串都是同一种。
2.对于连续的三个烤串，如果三种烤串都有，青菜不能放在中间（在吃肉中途吃菜是会令人自闭的）
3.依旧是对于连续的三个烤串，第一串和第三串都是青菜的话，中间不能是羊肉或者火腿肠（她的意思是吃素减肥）
现在有三种烤串都有无数根，她想摆出长度为n的烤串，请你求出方案数（由于结果可能会很大，所以只需给出答案模1000000007）
输入
第一行有一个数字T（T<100），表示有T组数据
接下来的T行，每行一个数字n (1≤N≤1010)
接下来的T行，每行一个数字n (1≤N≤1010)
输出
对于每一组数据，输出摆出长度为n的烤串的方案数
样例输入 复制
4
2
3
4
6样例输出 复制
9
20
46
244