题意
给定一个排列$p_{1},p_{2},/dots,p_{n}$，规定操作是选择两个数进行交换，设将排列变成$1,2,/dots,n$需要最少次数需要m次交换，
求出有多少次不同的操作达到升序排列的目标
答案模$10^{9} + 9$
$1 \leq n \leq 10^5$
题解
对于一个排列$p_{1},p_{2},/dots,p_{n}$，每个$i$ 向 $p_{i}$连一条边，那么可以得到$n$个点的无$n$条边的图，
并且图是由若干边组成。
引理：将一个长度为$n$的环边成$n$个自环，最少需要$n-1$次交换。
其中长度为n的环必然满足这样$2,3,/dots,n,1$ 的大小关系
引理的简单证明：
长度为$2$的环, 显然需要2次交换，
假设
原文：https://www.cnblogs.com/hhyx/p/12776578.html