题目描述

Guardian 的数学很差，但为了参加某次考试，他这次必须在数学上取得好成绩。在本学期的第一节课上，教授要求学生找出可以洗牌（有 $N$ 张牌）的方式数量，即只有一张牌与之前的位置相同，成功做到这一点的学生将在期中获得好成绩。帮助 Guardian 解决这个问题。

输入格式

输入以单行中的测试用例数量T开始。在接下来的T行中，每行都有一个整数 $N$。

输出格式

对于每个测试用例，您必须在一行中输出满足教授要求的可能方式的数量。由于答案可能是一个巨大的数字，只需将其模为 $10^7+9$ 即可输出。