Description
每天的11点20分，PIPI都会被一个问题困扰——中午去哪吃饭？
CSU有很多吃饭的地方，PIPI从中筛选出了4家性价比最高的——万福家菜馆，鲍汁黄焖鸡，3食堂，5食堂。
PIPI每天中午会选择其中一家就餐，现在PIPI想为接下来n天中午去哪吃饭都规划好，请你告诉PIPI有多少种方案？
PIPI觉得这个问题太简单了，所以它要求去万福家菜馆次数和去3食堂的次数都是偶数。
Input
第一行为T,代表数据组数.(1<=T<=1000)
接下来T行每行包括一个数字n,代表未来的n天需要规划。n<=1e18.
Output
每组数据输出一行一个整数，并对1e4+7取模。