Georgette Me, Georgette You (Problem G, CS3233 Midterm Contest 2025, 2025)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement

Mutsumi is currently playing with permutation arrays. What makes permutation arrays interesting to her is that for a permutation array of size $N$, all elements are integers between $0$ and $N - 1$ inclusive, and no two elements share the same value. This means it is possible to make another permutation array where each element’s value becomes the index and the original index becomes the element’s value. Formally, given a permutation array $P$ of size $N$, she can create another permutation array $Q$ of size $N$ where $Q_{P_i} = i$ for all $0 \le i < N$.

Mutsumi noticed that for some permutation arrays, applying the rule above produces a different permutation array. Excited by the prospect of seeing different permutations, she asks: How many permutation arrays of size $N$ are there such that when she creates another permutation array using her rule, the resulting array is different from the original array?

Mutsumi will ask $T$ questions, each question will correspond to a different $N$. Since the number of permutations can be very large, she simply asks you to give her the number in modulo $M$.

### Input

The first line of input contains two integers $T\ (1 \le T \le 10^6)$ and $M$ ($10^8 \le M \le 10^9 + 7$), the number of questions and the modulo respectively.

The next $T$ lines of the input contain one integer $N\ (1 \le N \le 10^6)$, the size of the permutation array in question.

### Output

Output $T$ lines, each line containing one integer corresponding to the answer.


# Sample Input #1
```
5 100000000
2
4
3
1000000
4
```
# Sample Output #1
```
0
14
2
24890624
14
```

Sample inputs:
5 100000000
2
4
3
1000000
4

Sample outputs:
0
14
2
24890624
14

# Solution Analysis

Let us solve the complementary problem: Count the number of permutations $P$ such that when a permutation $Q$ is defined as $Q_{P_i} = i$, $P_i = Q_i$ holds for all $i$.

We will show that for the above condition to be fulfilled, there must only be 1-cycles or 2-cycles in the permutation $P$:

- 1-cycles are such that $P_i = i$ for some $i$. It is clear when this is the case $Q_i = i$.
- 2-cycles are such that $P_{P_i} = i$ for some $i$. It can be checked by letting $P_i = k$ and $P_k = i$, we get $Q_k = i$ and $Q_i = k$, fulfilling the requirement.

Any permutation that does not consist fully of 1-cycles and 2-cycles must have a cycle of length of at least 3. This means that there exists a tuple $(a, b, c), a \ne c$, such that $P_a = b$ and $P_b = c$. When performing the operation on such a permutation, $Q_b = a \ne c = P_b$, these permutations do not satisfy the requirements of the problem.

We can use Dynamic Programming to count the number of permutations with only 1-cycles and 2-cycles. Let $DP[N]$ be the number of such permutations with length $N$.

- We can add a 1-cycle on top of a fulfilling permutation by appending the next missing element at the end of the permutation. That is, the permutation will be in the form of $[0, 1, \ldots, N - 2](N - 1)$ where the elements in square brackets represent a solved permutation. Hence, we have the transition  
  $DP[N] += DP[N - 1]$.

- We can add a 2-cycle on top of a fulfilling permutation of length $N - 2$. Let the 2-cycle be $(k, N - 1)$ for some $0 \le k < N - 1$. Then, the permutation can be in the form of $[0, 1, \ldots, k - 1](k + 1, \ldots, N - 2](k)$ where the elements in square brackets when joined represent a solved permutation. There are $N - 1$ possible choices of $k$, so we have the transition  
  $DP[N] += (N - 1) \times DP[N - 2]$.

The answer to the original problem is simply $N! - DP[N]$.


Special judge (C++ scorer):