Prime-smooth Sequence Parameter

You are given a sequence \(a_1, a_2, \ldots, a_n\) defined by:

• \(a_1 = 1\)
• \(a_2 = 2\)
• \(a_i = 2a_{i-1} + k\,a_{i-2}\) for \(3 \le i \le n\)

Here, \(n\) is the length of the sequence and \(k\) is a positive integer parameter chosen by someone named Little Z.

Little Z claims that the sequence is "Prime-smooth"; that is, for every prime number \(p \le n\) (except for a few counterexamples), the property

[ p \mid a_p ]

holds. However, after long experiments, you have discovered that there are exactly (m) primes (given as (p_i)) for which the property fails (i.e. (p \nmid a_p)). You believe that all other primes (p \le n) satisfy (p \mid a_p>.

Your task is to determine the smallest positive integer \(k\) such that for every prime \(p \le n\):

• If \(p\) is not among the \(m\) counterexample primes then \(a_p \equiv 0 \; (\bmod\; p)\);
• If \(p\) is one of the given counterexample primes then \(a_p \not\equiv 0 \; (\bmod\; p)\).

Since the answer can be very large, output the value of \(k \bmod c\), where \(c\) is a given prime.

inputFormat

The first line of input contains three integers \(n, m, c\) where:

• \(n\) (\(n \ge 3\)) is the length of the sequence.
• \(m\) is the number of primes for which the property fails.
• \(c\) is a prime number for modulo reduction.

The next \(m\) lines (or a single line with \(m\) numbers) contain \(m\) distinct prime numbers \(p_i\) (each \(\le n\)) which are the counterexamples.

outputFormat

Output a single integer, the smallest positive \(k\) (satisfying the conditions above) modulo \(c\).

sample

10 1 100
3

34