There are $n$ distinct positive integers $a_1, a_2, \cdots, a_n$ on a blackboard, all of which are less than $p$. Little J wants to play a guessing game with Little M using these numbers.
The rules of the game are very simple: at the beginning of the game, Little J randomly selects a non-empty subset of these numbers for Little M to guess. Little M can determine which numbers Little J has selected through a series of queries.
The format of each query is as follows: Little M can specify any number $a_k$. If $a_k$ is one of the numbers selected by Little J, Little J will tell Little M all the numbers in his selected set that can be represented as $(a_k)^m \bmod p$, where $m$ is any positive integer and $\bmod$ denotes the remainder after division. Conversely, if $a_k$ was not selected by Little J, Little J will simply tell Little M that $a_k$ was not selected.
The game ends immediately after Little M has identified all the numbers selected by Little J.
For example, if $n=4$, $p=7$, and the numbers $\{a_n\}$ in index order are $\{1, 3, 4, 6\}$, and Little J selects $\{1, 4, 6\}$, one possible (though not necessarily optimal) game process is as follows:
| Little M's Query | Little J's Feedback |
|---|---|
| $a_2 = 3$ | $a_2$ was not selected |
| $a_4 = 6$ | $6(= 6^1 \bmod 7)$, $1(=6^2 \bmod 7)$ |
| $a_3 = 4$ | $4(= 4^1 \bmod 7)$, $1(=4^3 \bmod 7)$ |
After 3 queries, all numbers selected by Little J are identified by Little M, and the game ends.
Little M still has homework to finish, so he needs to evaluate the time the game takes. He wants to know the expected value $S$ of the minimum number of queries required to end the game.
To avoid precision errors, you need to output the remainder of the answer multiplied by $(2^n - 1)$ modulo $998244353$. In this problem, you can assume that every time Little J selects a subset, he chooses one from all non-empty subsets of the set $\{a_1, a_2, \cdots, a_n\}$ with equal probability. Under this assumption, it can be proven that $(2^n - 1) \times S$ is always an integer.
Input
The first line contains two positive integers $n$ and $p$.
The second line contains $n$ positive integers, representing $a_1, a_2, \cdots, a_n$ in order.
Output
Output a single integer representing the answer.
Examples
Input 1
4 7
1 3 4 6Output 1
17Note 1
The table below shows the relationship between the subset selected by Little J and the minimum number of queries for Little M:
| Subset selected by Little J | Optimal query set |
|---|---|
| $\{1\}$ | $\{1 \}$ |
| $\{3\}, \{3, 4\}, \{3, 6\}, \{3, 4, 6\}, \{1, 3\}, \{1, 3, 4\}, \{1, 3, 6\}, \{1, 3, 4, 6\}$ | $\{3\}$ |
| $\{4\}, \{1, 4\}$ | $\{4\}$ |
| $\{6\}, \{1, 6\}$ | $\{6\}$ |
| $\{4, 6\}, \{1, 4, 6\}$ | $\{4,6\}$ |
Therefore, the expected value of the minimum number of queries is $S = \frac{17}{15}$.
Input 2
8 9
1 2 3 4 5 6 7 8Output 2
532Input 3
See game3.in and game3.ans in the provided files.
Subtasks
For all test cases: $1 \leq n \leq 5000$, $3 \leq p \leq 10^8$, $1 \leq a_i < p\ (1 \leq i \leq n)$, and all $a_i$ are distinct.
For all odd-numbered test cases, $p$ is guaranteed to be a prime number; for all even-numbered test cases, it is guaranteed that there exists an odd prime $q$ and a positive integer $k > 1$ such that $p = q^k$.
| Test Case ID | $n\leq$ | $p\le$ | Special Property | Test Case ID | $n\leq$ | $q\le$ | Special Property |
|---|---|---|---|---|---|---|---|
| $1$ | $10$ | $100$ | None | $2$ | $10$ | $100$ | None |
| $3$ | $10$ | $100$ | None | $4$ | $10$ | $100$ | None |
| $5$ | $200$ | $5000$ | None | $6$ | $200$ | $5000$ | None |
| $7$ | $300$ | $10^6$ | None | $8$ | $300$ | $10^6$ | None |
| $9$ | $300$ | $10^6$ | A | $10$ | $300$ | $10^6$ | B |
| $11$ | $5000$ | $10^7$ | A | $12$ | $5000$ | $10^7$ | None |
| $13$ | $5000$ | $10^7$ | None | $14$ | $5000$ | $10^7$ | None |
| $15$ | $5000$ | $10^8$ | A | $16$ | $5000$ | $10^8$ | B |
| $17$ | $5000$ | $10^8$ | None | $18$ | $5000$ | $10^8$ | None |
| $19$ | $5000$ | $10^8$ | None | $20$ | $5000$ | $10^8$ | None |
Special Property A: $3^i\ (1 \leq i \leq p - 1)$ are all distinct modulo $p$.
Special Property B: For all $1 \leq i \leq n$, $(a_i, p) > 1$.