牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出. 进阶：时间复杂度，空间复杂度

输入描述:

第一行输入一个正整数 T .表示有 T 组数据.接下来 T 行,每行输入一个正整数 n.11

输出描述:

输出 T 行,每一行对应每组数据的输出.