在这场比赛中取得如此成绩并非易事。通过解决之前的所有问题,你给众神留下了深刻的印象。因此,他们决定不告诉你这个问题的故事,而是给予正式的声明。
考虑 $$$n$$$ 代理。他们每个人最初都只有一件物品,第 $$$i$$$ 个代理的物品编号为 $$$i$$$。我们有兴趣在代理之间重新分配这些项目。当且仅当每个项目都分配给一个代理,并且每个代理都分配了一个项目时,分配才有效。
每个代理对项目都有偏好,这可以通过从最理想到最不理想的项目排列 $$$p$$$ 来描述。换句话说,当$$$i$$$出现在排列$$$p$$$中之前时,代理更喜欢项目$$$i$$$而不是项目$$$j$$$。偏好配置文件是每个长度为 $$$n$$$ 的 $$$n$$$ 排列的列表,使得第 $$$i$$$ 排列描述第 $$$i$$$ 代理的偏好。
某些特工可能对物品分配不满意。一组不满意的代理可能会选择不与其他代理合作。在这种情况下,他们只会在他们之间交换他们最初拥有的物品(第$$$i$$$个物品属于第$$$i$$$个代理人)。该群体的代理人并不关心该群体之外的代理人的满意度。然而,他们需要以这样一种方式交换他们的物品:至少让其中一个人更快乐,并且没有一个人不快乐(与给定的任务相比)。
正式地,考虑有效的项目分配 — $$$A$$$。让 $$$A(i)$$$ 表示分配给第 $$$i$$$ 个代理的项目。另外,请考虑代理的子集。令 $$$S$$$ 为其索引的集合。当且仅当存在有效分配 $$$B(i)$$$ 且满足以下条件时,我们会说该代理子集不满意:
- 对于每个 $$$i \in S$$$,$$$B(i) \in S$$$。
- S$$$ 中没有代理人 $$$i \in S$$$ 更喜欢 $$$A(i)$$$ 而不是 $$$B(i)$$$($$$S$$$ 中没有代理人不那么高兴)。
- S$$$ 中至少一名代理人 $$$i \in S$$$ 更喜欢 $$$B(i)$$$ 而不是 $$$A(i)$$$($$$S$$$ 中的至少一名代理人更满意)。
如果没有代理子集不满意,则分配是最佳的。请注意,空子集不能不满足。可以证明,对于每个偏好配置文件,都存在一个最佳分配。
示例:考虑具有以下偏好配置文件的 $$$3$$$ 代理:
1. $$$[2, 1, 3]$$$
2. $$$[1, 2, 3]$$$
3. $$$[1, 3, 2]$$$
这样的作业:
- 第一个特工获得物品 $$$2$$$
- 第二个特工获得物品 $$$3$$$。
- 第三位特工获得物品 $$$1$$$。
看到代理集 $$$\{1, 2\}$$$ 不满意,因为他们可以通过以下方式重新分配其(初始)项目:
- 第一个特工获得物品 $$$2$$$。
- 第二个特工获得物品 $$$1$$$。
- 第三位特工获得物品 $$$3$$$。
这种重新分配将使第二个代理更快乐,并且对第一个代理没有影响。结果,第三个特工得到了一个对他来说更糟糕的物品,但这并不能阻止集合 $$$\{1,2\}$$$ 不满意(他不在这个集合中)。
以下分配是最佳的:
- 第一个特工获得物品 $$$2$$$。
- 第二个特工获得物品 $$$1$$$。
- 第三位特工获得物品 $$$3$$$。
给定分配 $$$A$$$,计算分配 $$$A$$$ 最佳的不同偏好配置文件的数量。由于答案可能很大,因此输出它对 $$$10^9+7$$$ 取模。
两个偏好配置文件是不同的,前提是它们为任何代理分配了不同的偏好排列。
输入
在输入的第一行中有一个整数 $$$n$$$ ($$$1 \leq n \leq 40$$$)。下一行包含 $$$n$$$ 空格分隔的整数,即从 $$$1$$$ 到 $$$n$$$ 的数字排列。第 $$$i$$$ 数字表示在最佳分配中分配给代理 $$$i$$$ 的项目。
输出
在单行中输出一个非负整数,即输入中给定的项目分配以 $$$10^9+7$$$ 为模的最佳偏好配置文件的数量。
示例
输入 #1
2 2 1
输出 #1
1
输入 #2
3 1 2 3
输出 #2
98
输入 #3
4 2 1 3 4
输出 #3
27408
注意
第一个测试用例的分配仅对于以下首选项配置文件是最佳的:
$$$2, 1$$$
$$$1, 2$$$
如果任何代理最想要他的初始项目并获得另一个项目,他将形成一个不满意的集合。因此,对于任何其他偏好配置文件来说,分配都不是最佳的。