棋子

小宇最近有点无聊，她看到自己之前买的五子棋，就想起用栈来玩一个游戏。五子棋有黑白棋子，每次小宇会向栈里放一个棋子，如果栈顶三枚棋子的颜色一样，小宇就会把这三枚棋子取出，继续放棋子，直到栈里没有任何棋子。好奇宝宝小宇想知道，有多少种不同的颜色顺序能够满足条件。你只需要告诉她结果除以1,000,000,007的余数即可。

输入的第一行为一个整数T (1<=T<=50)，表示测试用例的个数。
接下来的每行输入一个整数N(N<=1,000)，表示N个棋子。

输出T行数字，每行一个整数K，表示结果除以1,000,000,007的余数。

1
3

2

中科院计算所第二届“斯伦贝谢”杯Debug大赛