Description

Xiao Z gave you a sequence. Specifically, $a_1=1$, $a_2=2$, and $a_i=2a_{i-1}+ka_{i-2}(3\le i\le n)$, where $n$ is the length of the sequence, and $k$ is a positive integer parameter she set.

Xiao Z told you a secret: this sequence was carefully chosen by her and has a wonderful property called "Prime-smooth"—that is, for any prime $p$ not exceeding $n$, it holds that $p\mid a_p$ ($\mid$ denotes divisibility).

You were curious whether this was really true, so you wrote a prime generator and tried for three days and three nights. Finally, you found a few counterexamples: there are $m$ primes $p_i$ that do not satisfy the property Xiao Z mentioned.

Since you have randomized for a long time, you believe that other primes must satisfy the property.

To show that you and Xiao Z think alike, you now want to guess the parameter $k$ that Xiao Z set back then. Since the answer is very large, you only need to output the minimum $k$ modulo a prime $c$.

Input Format

The first line contains three non-negative integers $n,m,c$, with the same meanings as in the statement.

The next $m$ lines each contain a positive integer $i$, meaning that the $i$-th prime in increasing order, $p_i$, does not satisfy $p_i\mid a_{p_i}$. We guarantee that this prime $p_i\le n$. Note: it is not guaranteed that these $m$ numbers are pairwise distinct.

Output Format

Output one integer: the value of the minimum $k$ modulo $c$.

In particular, if there is no solution, output $-1$.

10 1 998244353
3

20

40 2 1018429441
1
4

-1

Hint

Sample 1 Explanation

Note that the 3rd prime is $5$.

When $k=20$, $a_2=2$, $a_3=24$, and $a_7=19264$ all satisfy $p\mid a_p$, and $a_5=656$ satisfies $p\nmid a_p$.

Constraints

$10\le n\le 3\times 10^8$.

$n\lt c\lt 2^{30}$, $c=a\cdot 2^d+1(d\ge 18)$, and it is guaranteed that $c$ is prime.

$0\le m\le 20$.

Translated by ChatGPT 5