百度外卖“附近的餐厅”展示的是一个 N 行 4 列的网格，里面放的原本都是占 1 行 1 列的正方餐厅广告，新来的设计师du熊同学正在考虑一种新的设计方案，来更好的展示附近的餐厅。

作为设计师的du熊希望在 N 行 4 列的网格里先行放入若干占 1 行 1 列的正方餐厅广告，使得剩下来的空间，可以被占 1 行 2 列或 2 行 1 列的长条餐厅广告完美覆盖。du熊希望让你帮他确定，到底有多少种放置若干正方餐厅广告的方案，使得放置若干正方餐厅广告以后剩下的空间可以被若干 1 行 2 列或 2 行 1 列的长条餐厅广告完美覆盖。

完美覆盖即每个没有放入正方餐厅广告的位置会被长条餐厅广告覆盖恰好一次，且广告不可超出页面边界（如果所有的位置都已放入正方餐厅广告也属于完美覆盖）。

因为方案数会很多，我们希望你输出方案数对 1,000,000,007 取模的结果。

输入格式

输入第一行为一个整数 T (1 ≤ T ≤ 20)，表示数据组数。

接下来一共 T 行，每行为一个正整数 N (1 ≤ N ≤ 10¹⁸)，代表页面的长度。

对于简单版本，1 ≤ n ≤ 6；

对于中等版本，1 ≤ n ≤ 1000；

对于困难版本，1 ≤ n ≤ 10¹⁸。

输出格式

一共输出 T 行，每行输出该组数据对应的方案数对 1,000,000,007 取模的结果。