스왑 횟수 세기 (Hard)

어제와 마찬가지로 (연습 세션의 문제 U) Bob은 바빠서 Alice는 1인용 게임과 퍼즐을 계속 하고 있습니다. Alice의 최신 퍼즐에는 1부터 $n$까지의 수로 이루어진 순열이 있습니다. 목표는 가능한 한 가장 적은 횟수의 swap으로 순열을 정렬하는 것입니다.

Alice는 퍼즐을 그냥 푸는 대신, 무작위로 두어서 이길 확률이 궁금합니다. 이를 계산하려면 퍼즐의 최적 해의 개수가 필요합니다.

1부터 $n$까지의 수로 이루어진 순열 $p_1, \ldots, p_n$이 주어집니다. 각 단계에서 두 수 $x < y$를 골라 $p_x$와 $p_y$를 교환할 수 있습니다.

$m$을 주어진 순열을 정렬하는 데 필요한 swap의 최소 횟수라고 합시다. 주어진 순열을 정렬하는, 정확히 $m$번의 swap으로 이루어진 서로 다른 수열의 개수를 구하세요. 이 값이 클 수 있으므로 $10^9 + 9$로 나눈 나머지를 출력합니다.

첫 줄에는 테스트 케이스의 개수 $t$가 주어집니다. 각 테스트 케이스 앞에는 빈 줄이 있습니다.

각 테스트 케이스는 두 줄로 이루어집니다. 첫 줄에는 정수 $n$이, 둘째 줄에는 $1, \ldots, n$의 순열 $p_1, \ldots, p_n$이 주어집니다.

각 테스트 케이스마다, 가장 적은 횟수의 swap으로 주어진 수열을 정렬하는 방법의 수 $x$를 $10^9 + 9$로 나눈 나머지를 한 줄에 정수 하나로 출력합니다.

$1 \le n \le 10^5$

첫 번째 테스트 케이스에서는 두 번의 swap으로 순열을 정렬할 수 있습니다. 첫 번째 swap은 어떻게 골라도 되고, 각각에 대해 최적의 두 번째 swap은 정확히 하나입니다. 예를 들어 가장 짧은 해 중 하나는 "$p_1$과 $p_2$를 교환한 다음 $p_1$과 $p_3$를 교환"입니다.

두 번째 테스트 케이스에서는 최적 해가 $p_1$과 $p_2$를 교환하고 $p_3$와 $p_4$를 교환하는 것입니다. 이 두 swap은 어느 순서로 해도 됩니다.

세 번째 수열은 이미 정렬되어 있습니다. 최적 swap 횟수는 0이므로, 최적 해는 빈 swap 수열 하나뿐입니다.