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