SP13523 GUMATH2 - Card Meets (medium)

Guardian 的数学成绩不佳，但为了在这次考试中取得好成绩，他必须要提升数学能力。在学期的第一堂课上，教授要求学生们设计一种方法来洗牌一副有 $N$ 张牌的牌组，使得恰好只有一张牌的顺序保持不变。任何能够顺利完成这个任务的学生将在期中考试中获得高分。请帮助 Guardian 找到解决方案。

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行包含一个整数 $N$，表示牌组的张数。

对于每个测试用例，输出一行结果，表示满足教授要求的洗牌方式数。由于结果可能非常大，请对 $10000009$ 取模后输出。

- $1 \le T \le 10^5$ - $1 \le N \le 10^5$ **本翻译由 AI 自动生成**