Q11091: How many Knight Placing?
給你一個 6*n 的棋盤。這並不是一個標準的棋盤，這個棋盤的列數是可變的。你必須在每一列放剛好兩個騎士，所以你總共要放 2*n 個騎士；你要計算有幾種放置方式是合法的。如果任兩個騎士不能互相攻擊，那種放置方式就是合法的。 (在(x,y)的騎士可以攻擊在 (x±2,y±1) 和在 (x±1,y±2)的騎士。)
Input
第一行有一個數字 T(T ≤ 15)表示測資有幾組。每個測資都包含一個整數 n(1 ≤ n < 1000000000)。
Output
對每組測資輸出合法的放置方式有幾種。答案可能會非常大，所以輸出答案%10007 就好。
Sample Input Sample Output 
4
1
10
100
1000
 
15
178
30
8141
Translated by DarkKnight