ADACHES2  Ada and Palaces
Ada the Ladybug was playing chess 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
Input
The first line of input will contain 1 ≤ T ≤ 10^{5}, the number of testcases.
Each of the testcases will contain single integer 1 ≤ N ≤ 10^{7}, the size of chessboard.
Output
For each testcase output the number of possibilities modulo 1000000007.
Example Input
8 1 2 3 7 10 1000 10000 9999999
Example Output
1 0 0 646 479306 711794305 450342414 838796194
hide comments
shashankpathak:
20181022 14:58:27
How can one give this question under dp category when its formula based on series 

kshubham02:
20180730 17:33:10
I did spoj toolkit and then OEIS, and finally did not submit my code. How do you even expect people to come up with that sort of crazy formula on their own!? Last edit: 20180730 17:33:49 

morass:
20180628 14:28:15
@va1ts7_100: Hi, well, as you pointed out.. don't gu futher than to "N" as parameter (yet indeed not a short way from here [well, in code it is, but.. :P ]) 

va1ts7_100:
20180330 20:01:40
I guess this problem involves dp with bit mask , but because of large value of n , I can't figure out how to create dp state . Can anyone give me some pointers to it @morass ? Last edit: 20180330 20:06:35 

morass:
20171027 20:48:39
@Nitesh Bagmar: Good day to you... The judge data contains much more than 8 testcases ..try to debug (for example take peek at first 36 testcases ;) ) 

Nitesh Bagmar:
20171027 19:08:10
@morass: can you please check submission# 20466914 once. It gives correct answer for each of the given cases and I don't see why it will give wrong answer unless the given input criteria is incorrect. 

morass:
20171023 01:31:21
@Min_25: Thank you so much.. repaired! ^_^ 

Min_25:
20171023 01:19:28
In the sample case, T should be 8 instead of 9. Last edit: 20171023 01:23:23 
Added by:  Morass 
Date:  20171022 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 