[ARC176] D - Swap Permutation

D - Swap Permutation

Time Limit: 4 sec / Memory Limit: 1024 MB

分数: 700 分

题面

给定一个的排列。你将进行以下操作次：

• 选择整数对，满足，并交换和。

共有种可能的操作序列。
对于每一种序列，考虑在所有操作之后的值。找出所有这些值的和对取模的结果。

限制条件

• 是的一个排列。

---

输入

输入从标准输入中获取，格式如下：

输出

输出答案。

---

输入样例 1

3 1
1 3 2

输出样例 1

8

有三种可能的操作序列：

• 选择，得到。
• 选择，得到。
• 选择，得到。

这些情况下的值分别为，，。因此，答案为。

---

输入样例 2

2 5
2 1

输出样例 2

1

---

输入样例 3

5 2
3 5 1 4 2

输出样例 3

833

---

输入样例 4

20 24
14 1 20 6 11 3 19 2 7 10 9 18 13 12 17 8 15 5 4 16

输出样例 4

203984325