#P12286. [蓝桥杯 2024 国 Java A] 空间传送装置

[蓝桥杯 2024 国 Java A] 空间传送装置

题目描述

蓝桥王国拥有 4242 座城市以及 4242 位骑士。这些骑士按照 114242 的编号顺序,分别居住在对应编号的城市中。即第 11 位骑士居住在城市 11,第 22 位骑士居住在城市 22,依此类推。

最近,王国中引入了一项革命性技术:空间传送装置。该装置可以根据一个长度为 4242 的数字排列 aa,将所有骑士一次性传送至新的城市。

排列 aa 必须由 1421 \sim 424242 个数字组成,且每个数字只出现一次。在传送操作中,位于城市 iii=1,2,3,,42i = 1, 2, 3, \cdots, 42)的骑士会被传送到城市 aia_i。例如,如果 a1a_1 的值为 33,那么当前位于城市 11 的骑士会被传送至城市 33

为测试技术的可靠性,王国决定连续 20242024 天每天使用同一排列 aa 进行一次传送操作。

小蓝负责为这次测试设计排列 aa,她的目标是确保所有骑士在经过 20242024 天传送后,都能返回自己的起始城市。而在此之前的任何一天,不会出现所有骑士都回到起始城市的情况。

请问,有多少种不同的数字排列 aa 能满足小蓝的需求?由于答案可能很大,因此你只需要将答案对 109+710^9 + 7 取模后提交即可。

数字排列 aa 是由 1142424242 个数字按照一定顺序排列而成的序列。每个数字在排列中只能出现一次,且所有数字必须全部包含在排列中。

如果两个排列中至少有一个位置上的数字不同,则这两个排列被视为不同的数字排列。例如,{1,2,3,,42}\{1, 2, 3, \cdots, 42\}{1,3,2,,42}\{1, 3, 2, \cdots, 42\} 就是不同的数字排列,因为它们在第二个位置上的数不相同。

输出格式

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只需要编写一个程序输出这个整数,输出多余的内容将无法得分。