Description

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:

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.

Input Format

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 Format

Output a single integer in one line, representing the answer.

4 7
1 3 4 6

17

8 9
1 2 3 4 5 6 7 8

532

Hint

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:

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$.

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