405166: GYM101808 F Random Sort

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Random Sorttime limit per test1.0 smemory limit per test256 megabytesinputstandard inputoutputstandard output

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 Api for each 1 ≤ i ≤ n.

In other words sorting the array A1, A2, ..., An results in the array Ap1, Ap2, ... , Apn

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?

Input

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 Ai, the array that needs to be sorted. (1 ≤ Ai ≤ 1000)

Output

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.

ExampleInput
2
3
1 2 3
2
5 5
Output
1
2
Note

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

加入题单

上一题 下一题 算法标签: