P6197 [EER1] 礼物

### Update： 时限扩大到 3 秒。

小 Z 送了你一个数列，具体的，有 $a_1=1$，$a_2=2$，$a_i=2a_{i-1}+ka_{i-2}(3\le i\le n)$，其中 $n$ 是数列的长度，$k$ 是她设定的一个正整数参数。 小 Z 告诉你一个秘密，这个数列是她精心挑选的，有着一种奇妙的性质 "Prime-smooth"—— 即对于 $n$ 以内的任何一个**质数** $p$，满足 $p\mid a_p$（$\mid$ 是整除记号）。 你很好奇是不是真的有这回事，于是你写了一个质数发生器，进行了长达三天三夜的尝试，终于发现了几个反例：有 $m$ 个质数 $p_i$ 竟然不满足小 Z 所说的性质！ 由于你已经随机了很久，你相信别的质数 **一定满足** 性质。 为了表明你和小 Z 心有灵犀，你现在想猜出小 Z 当时设定的参数 $k$，由于答案很大，你只需要求出最小的 $k$ 对一个质数 $c$ 取模即可。

第一行三个非负整数 $n,m,c$，它们与题面中含义相同。 接下来 $m$ 行，每行一个正整数 $i$，表示对于从小到大数第 $i$ 个质数 $p_i$，不满足 $p_i\mid a_{p_i}$。我们保证这个质数 $p_i\le n$。注意：**不保证**这 $m$ 个数两两不同。

一行一个整数，为最小的 $k$ 对 $c$ 取模后的值。 特别的，如果出现无解的情况，输出 $-1$。

**【样例 1 解释】** 注意第 $3$ 个质数是 $5$。 当 $k=20$ 时，$a_2=2$，$a_3=24$，$a_7=19264$ 均符合 $p\mid a_p$，并且 $a_5=656$ 符合 $p\nmid a_p$。 **【数据范围】** $10\le n\le 3\times 10^8$。 $n\lt c\lt 2^{30}$，$c=a\cdot 2^d+1(d\ge 18)$，保证 $c$ 是质数。 $0\le m\le 20$。 | 子任务编号 | $n\leq$ | $m\leq$ | 特殊性质 | 分值 | | :--------: | :------------: | :------------: | :------------: | :--: | | 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 |