405166: GYM101808 F Random Sort

Saeed is teaching Algorithms 1 at Damascus University, his last lecture was about sorting algorithms. As homework, he gave the students an array A of length n and asked them to sort it in increasing order.

Shahhoud fell asleep during the lecture, so he doesn't know how to sort the array. He decided to create his own algorithm, Random Sort. He first chooses a permutation p of length n (A permutation of length n is an array of length n where each integer between 1 and n appears exactly once).

After that, he decides that the sorted array is A_pi for each 1 ≤ i ≤ n.

In other words sorting the array A₁, A₂, ..., A_n results in the array A_p1, A_p2, ... , A_pn

This algorithm does not always sort the array correctly. Shahhoud is wondering about the number of ways he can choose a permutation p that results in a correctly sorted array. Since the number can be very large, he wants to calculate it modulo 7901. Can you help him?

The first line contains a single integer T, the number of test cases.

Each test case starts with a single line that contains an integer n, the length of the array A. (1 ≤ n ≤ 1000)

The next line contains n space-separated integers A_i, the array that needs to be sorted. (1 ≤ A_i ≤ 1000)

For each test case, print one line containing one integer, the number of ways of choosing a permutation p that correctly sorts the array A in increasing order. Print the answer modulo 7901.

2
3
1 2 3
2
5 5

1
2

Two permutations P and Q are considered different if P_i ≠ Q_i for any 1 ≤ i ≤ n