# CQXYM Count Permutations solution codeforces

CQXYM is counting permutations length of .

A permutation is an array consisting of  distinct integers from  to  in arbitrary order. For example,  is a permutation, but  is not a permutation ( appears twice in the array) and  is also not a permutation ( but there is  in the array).

## CQXYM Count Permutations solution codeforces

A permutation (length of ) will be counted only if the number of  satisfying  is no less than . For example:

• Permutation  will count, because the number of such  that  equals  (, , ).
• Permutation  won’t count, because the number of such  that  equals  ().

CQXYM wants you to help him to count the number of such permutations modulo  ().

In addition, modulo operation is to get the remainder. For example:

• , because ,
• , because .

### Input CQXYM Count Permutations solution codeforces

The input consists of multiple test cases.

The first line contains an integer  — the number of test cases. The description of the test cases follows.

Only one line of each test case contains an integer .

It is guaranteed that the sum of  over all test cases does not exceed

## Output CQXYM Count Permutations solution codeforces

For each test case, print the answer in a single line.

Example
input

Copy
4
1
2
9
91234


## Copy

1
12
830455698
890287984


## Note CQXYM Count Permutations solution codeforces

, there is only one permutation that satisfies the condition:

In permutation , and there is one  satisfy the condition. Since , this permutation should be counted. In permutation . Because , this permutation should not be counted.

, there are  permutations: