Palace
Time limit2sMemory limit512 MB
Count ways to place N non-attacking palace pieces (rook plus king moves) on an N by N board, modulo 1,000,000,007, for up to 1,000,000 test cases with N up to 10,000,000.
- Level
Medium6 of 10
- Topics
- Math, Combinatorics, Array, Dynamic programming
- Solved
- No attempts yet
Problem
Gusagwa, tired of chess, invented a new chess piece.
The new piece is called a "palace". A palace can move both like a rook and like a king. That is, it can move to any square in the same row or column, or to any of the four adjacent squares and four diagonal squares.
Write a program that finds the number of ways to place N palaces on an N×N chessboard. The palaces placed on the board must not attack each other.
Input
The first line gives the number of test cases T (1 ≤ T ≤ 1,000,000). Each test case is given on its own line and contains the board size N (1 ≤ N ≤ 10,000,000).
Output
For each test case, print the number of ways to place N palaces modulo 1,000,000,007.