亚洲赛要结束了，yyf决定干点正事了——追妹子。yyf有一长串的喜欢的妹子的名单。他打算把妹子的名字用带颜色的笔记录在一长条纸条上。为了表示他对每个妹子独一无二的爱，他不想让纸条上出现相邻妹子名字颜色相同的情况

现yyf有三支笔，n(n<=10000)个喜欢的妹子。

请问他有多少种书写方案。

ps：由于答案数字较大，请对10007取余后输出

第一行为T，表示样例组数（T<=500000）

每组样例为一个数字n

输出方案总数