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

多组样例

第一行一个整数T(1<=T<=20)

代表测试样例数

接下来t行每行一个整数n，代表ledestin要请BanFcc吃n天饭(1<=n<=100000)

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

Author  Mr.Lee