| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 2048 MB | 0 | 0 | 0 | 0.000% |
You are given a permutation $p$ consisting of $n$ integers from $1$ to $n$. You want to build a sequence $a$ from $p$. To do that, you perform the following operation $n$ times:
You are given a random permutation $p$. Your task is to calculate the number of different sequences $a$ that can be obtained in the way described above. This number can be very large, so find it modulo $998\,244\,353$. Two sequences are different if there is a position at which these sequences differ.
A permutation of size $n$ is a sequence of $n$ distinct integers from $1$ to $n$.
The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^5$), the number of test cases. The test cases follow.
The first line of each test case contains an integer $n$, the size of the permutation ($1 \le n \le 2 \cdot 10^5$). The next line contains the permutation itself: $n$ distinct integers from $1$ to $n$. The permutation is generated using a pseudorandom number generator.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case, output a line with a single integer: the required number modulo $998\,244\,353$.
4 5 4 3 5 1 2 5 5 3 1 2 4 2 2 1 3 1 3 2
8 7 2 4