You are given a 6 ∗ n chessboard. Yes it is not a regular chessboard. The number of columns in this chessboard is variable. In each of the columns you have to place exactly 2 knights. So you have to place total 2 ∗ n knights. You have to count the number of valid placing of these 2 ∗ n knight. A placing is invalid if any of the 2 knights attack each other. Those who are not familiar with knight moves “A knight in cell(x,y) attacks the knights in the cell (x±2,y±1) and cell (x±1,y±2)”. Input The first line of the input contains a single integer T indicating the number of test cases. Each test case contains a single integer n. Output For each test case output an integer the number of valid placing. The integer may be very large. So just output the result% 10007. Constraints • T ≤ 15 • 1 ≤ n < 1000000000 Sample Input 4 1 10 100 1000 Sample Output 15 178 30 8141