作为队伍的核心，forever97很受另外两个队友的尊敬。
Trote_w每天都要请forever97吃外卖，但很不幸的是宇宙中心forever97所在的学校周围只有3家forever97爱吃的外卖。
如果Trote_w给forever97买了别家的外卖，forever97就会大喊“我不吃我不吃”。
但是forever97又不喜欢连续三天吃一种外卖。
如果Trote_w哪天忘了这件事并且三天给他买了同一家外卖，那么forever97就会把Trote_w的头摁进手机屏幕里。
作为Trote_w的好朋友，你能告诉他连续请forever97吃n天饭，有多少不同的购买方法吗？

多组样例
第一行一个整数T(1<=T<=20)代表测试样例数
接下来t行每行一个整数n，代表Trote_w要请forever97吃n天饭(1<=n<=100000)

输出T个整数代表方案数，由于答案太大，你只需要输出mod 1e9+7 后的答案即可。

动态规划-线性