题目背景

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

10 1 998244353
3

20

40 2 1018429441
1
4

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