Jackson, after witnessing the advancements in the world of technology, decided to sell his small cozy house and enroll in the programming-and-algorithm micromaster. He came across an interesting algorithm that he needed to analyze and solve the problem related to it, in order to pass the exam at this stage of the course. The pseudocode of this algorithm is as follows:
He wants to know for how many permutations of length from the possible ones, the final permutation will be sorted after running this algorithm.
输入格式
The first line contains an integer (), the number of test cases.
Each of the next lines contains an integer (), representing the length of the permutation for the test case.
输出格式
Output lines. On the line, print the number of permutations of length which will be sorted after running the provided algorithm on it. Since the output could be very large, output the result modulo .
