P6197 [EER1] Gift

### Update: The time limit has been increased to 3 seconds.

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

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 one integer: the value of the minimum $k$ modulo $c$. In particular, if there is no solution, output $-1$.

**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$. | Subtask ID | $n\leq$ | $m\leq$ | Special Property | Score | | :--------: | :------------: | :------------: | :--------------: | :---: | | 1 | $10^6$ | $20$ || 10 | | 2 | $5\times 10^7$ | $20$ || 20 | | 3 | $2\times 10^8$ | $0$ || 10 | | 4 | $2\times 10^8$ | $6$ || 10 | | 5 | $3\times 10^8$ | $0$ | $c=998244353$ | 20 | | 6 | $3\times 10^8$ | $0$ || 20 | | 7 | $3\times 10^8$ | $20$ || 10 | Translated by ChatGPT 5