SP33059 ADACHES2 - Ada and Palaces

Ada the Ladybug was playing [chess](https://en.wikipedia.org/wiki/Chess_piece) agains her good friend Velvet Mite Vinit. They came up with new figure, called **palace**. In fact, palace is just **tower** with **king** inside. It can attack as king and tower combined: Either anywhere to same column or row **or** anywhere to adjacent (by side or diagonal) field. Their question is simple: How many ways can **N** palaces be placed on **NxN** chessboard so none of them attacks any other. Since this number might be pretty big, output answer modulo **10 $ ^{9} $ +7**

The first line of input will contain **1 , the number of test-cases.** Each of the testcases will contain single integer **1 , the size of chessboard.**

For each test-case output the number of possibilities modulo 1000000007.