Arpa and his friends are in a construction camp, their mission is to build and repair houses for poor people. Mojtaba is their commander. Totally there are $$n!$$ groups of students in camp, each group containing $$n$$ students. Camp lasts for $$\frac{n! \times (n! - 1)}{2}$$ days. Every they at 6 am Mojtaba rings the morning bell, all of the groups stand in their row. In each group, every person has an id from 1 to $$n$$, ids are unique. Also, groups are unique, i.e. there are no two groups with the same lineup. For example, if n = 3, here is the lineups:

• Group #1: 1 2 3
• Group #2: 1 3 2
• Group #3: 2 1 3
• Group #4: 2 3 1
• Group #5: 3 1 2
• Group #6: 3 2 1

After the national anthem, Mojtaba chooses 2 groups, persons with the same position and id in these two groups join each other and go for construction. Mojtaba never chooses the same pair of groups. Can you determine how many pairs of students will go to construction till the end of camp? Print the answer modulo $$M$$.

In short, you need to determine the summation of the number of positions containing the same element, over all distinct unordered pairs of permutations of size $$n$$. 

Input Format

The first line contains two integers, t, M (\(1 \leq t \leq 2 \times 10^5, 1 \leq M \leq 10^9 + 17\)) -- the number of test cases and modulo.

Each test case contains an integer n (\(1 \leq n \leq 5 \times 10^6\)).

Output Format

For each test case print the answer.