Count of Beautiful Sequences

You are given a positive integer n and a set A of m integers. A sequence a₁, a₂, ..., a_n is said to be beautiful if for every adjacent pair of elements the sum is a prime number; in other words, for every 1 ≤ i < n, the condition \[ a_i + a_{i+1}\text{ is prime} \] must hold true.

Your task is to compute the number of beautiful sequences of length n in which every element is chosen from the set A. Since the answer can be very large, you should output it modulo \(10^9+7\).

Input Format: The first line contains two space-separated integers n and m. The second line contains m space-separated integers representing the set A.

Output Format: Output a single integer — the number of beautiful sequences modulo \(10^9+7\).

inputFormat

The input begins with a line containing two integers n and m. Here, n is the desired length of the sequence and m is the number of elements in the set A. The second line contains m space-separated integers that represent the set A.

For example:

3 3
1 2 3

outputFormat

Output a single integer — the total count of beautiful sequences of length n modulo \(10^9+7\).

sample

1 3
1 2 3

3