P6730 [WC2020] Number Guessing Game.

There are $n$ pairwise distinct positive integers $a_1, a_2, \cdots, a_n$ written on the blackboard, all smaller than $p$. Little J wants to use these numbers to play a number guessing game with Little M. The rules are very simple. At the start of the game, Little J will randomly choose some of these numbers for Little M to guess. Little M can determine which numbers Little J chose by making several **queries**. Each **query** works as follows: Little M may specify any number $a_k$. If it is one of the numbers chosen by Little J, then Little J will tell Little M all numbers among his chosen numbers that can be written as $(a_k)^m \bmod p$, where $m$ is any positive integer, and $\bmod$ denotes the remainder after division. Otherwise, if $a_k$ was not chosen by Little J, then Little J will only tell Little M that $a_k$ was not chosen. The game ends immediately after Little M has determined all numbers chosen 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 chooses $\{1, 4, 6\}$, then one possible process (not necessarily optimal) is: | Little M's query | Little J's response | | ---------------- | -------------------------------------------- | | $a_2 = 3$ | $a_2$ was not chosen | | $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, Little M has determined all numbers chosen by Little J, and the game ends. Little M still has homework to finish, so he needs to estimate the time spent in the game. He wants to know the expected value $S$ of the minimum number of queries he needs to make in order 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 may assume that each time Little J chooses numbers, he selects uniformly at random among all **non-empty subsets** of $\{a_1, a_2, \cdots, a_n\}$. Under this assumption, it can be proven that $(2^n - 1) \times S$ is always an integer.

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 a single integer in one line, representing the answer.

#### Sample 1 Explanation The table below shows the relationship between the subset chosen by Little J and the minimum number of queries for Little M: | Subset chosen by Little J | Optimal set of queries | | ------------------------------------------------------------ | ---------------------- | | $\{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 minimum number of queries is $S = \frac{17}{15}$. #### Constraints For all test points: $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 pairwise distinct. For all test points with odd indices, $p$ is guaranteed to be a prime; for all test points with even indices, it is guaranteed that there exists an odd prime $q$ and an integer $k > 1$ such that $p = q^k$. | Test point ID | $n\leq$ | $p\le$ | Special property | Test point ID | $n\leq$ | $p\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: Modulo $p$, $3^i\ (1 \leq i \leq p - 1)$ are pairwise incongruent. Special property B: For all $1 \leq i \leq n$, $(a_i, p) > 1$. Translated by ChatGPT 5