Gzh觉得天天都上自习的日子实在是太无聊了，所以他决定他这次上自习就会是他最后一次上自习了。
众所周知，Gzh上自习的方式和他去的自习室总是与众不同的，这次也不例外。
Gzh这次要去的自习室，每个自习室有n个小房间(3<=n<=100000)，每个小房间可以坐1-6个人，相邻的两个房间的人数之差不能大于4且至少有三个容量不同的小房间，那么，Gzh想知道自习室的小房间数目为n时，自习室构造的所有情况。结果对7777777取模。
第一个数为数据组数t 接下来n行，每行1个整数n
对于每组数据，输出一行，为自习室小房间数目为n时，自习室所有可能的构造的数量。
1
3104