SP10557 MINI - MINI IN DANGER!!!

在一个 $n \times n$ 的棋盘上，汤姆正在玩一款数字游戏。游戏要求用从 $0$ 到 $n-1$ 的数字填满棋盘的 $n \times n$ 个小格子。游戏规则规定，每一行和每一列的数字之和必须能被 $n$ 整除。 汤姆已经将棋盘设置成了一个符合规则的胜利配置。然而，他聪明又调皮的女儿米妮改变了棋盘上的数字。现在，米妮很害怕，因为她的爸爸快要回家了。她意识到，如果爸爸看到当前的棋盘配置不符合规定，可能会责骂她。米妮想知道，有多少种方法可以将棋盘恢复到符合规则的胜利配置。请帮帮她。

第一行输入一个整数 $T$，表示测试用例的数量。接下来的每一行包含一个整数 $N$，表示棋盘的大小。

对于每个测试用例，输出将棋盘恢复到胜利配置的方法数，答案对 $1000000009$ 取模后输出到一行中。

- $T \leq 10^6$ - $1 \leq N \leq 2^{64} - 1$ - $N$ 不是 $1000000009$ 的倍数 **本翻译由 AI 自动生成**