Company: TBO
Difficulty: hard
Tech Club The Tech Club keeps a register of K K students. A student is identified by a pair of skill levels: student (r, c) has Mathematics skill r and Physics skill c , where r and c each run over 0, 1, ..., K-1 . Exactly one student holds each pair, so the register is a K K grid. A committee is an unordered set of exactly N distinct students. A committee is valid when every pair of its members satisfies all three rules: their Mathematics skills differ; their Physics skills differ; the absolute difference of their Mathematics skills is not equal to the absolute difference of their Physics skills. Reading the register as a grid, the first two rules say that no two chosen members share a row or a column, and the third says that no two chosen members lie on a common diagonal. You are given Q independent queries. For each query, count the valid committees of size N on a K * K register and report the count modulo 1000000007 . Input Format The first line contains a single integer Q , the nu