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 109+7

Input

The first line of input will contain 1 ≤ T ≤ 105, the number of test-cases.

Each of the testcases will contain single integer 1 ≤ N ≤ 107, the size of chessboard.

Output

For each test-case 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: 2018-10-22 14:58:27

How can one give this question under dp category when its formula based on series

kshubham02: 2018-07-30 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: 2018-07-30 17:33:49
morass: 2018-06-28 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: 2018-03-30 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: 2018-03-30 20:06:35
morass: 2017-10-27 20:48:39

@Nitesh Bagmar: Good day to you... The judge data contains much more than 8 test-cases ..try to debug (for example take peek at first 36 test-cases ;-) )

Nitesh Bagmar: 2017-10-27 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: 2017-10-23 01:31:21

@Min_25: Thank you so much.. repaired! ^_^

Min_25: 2017-10-23 01:19:28

In the sample case, T should be 8 instead of 9.

Last edit: 2017-10-23 01:23:23

Added by:Morass
Date:2017-10-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All