You are given an integer \(P\).

Also, you are given \(Q\) queries of the following type:

• \(N\): Determine the count of distinct arrays of size \(\le N\) and \(\ge 1\) such that:
  • Each array element is a prime number
  • Product of the value of all the array elements is \(\le P\)
  • Array formed is palindromic

Note

• Two arrays are said to be distinct if there exists at least one index where the value of element present in both the arrays is different.
• An array is said to be palindromic if it reads same from the left to right and right to left direction.
• Since the count can be very large, print the output in modulo \(10^9 + 7\).
• Assume \(1\) based indexing.

Input format

• The first line contains an integer \(P\).
• The second line contains an integer \(Q\).
• The next line contains \(Q\) space-separated integers that denotes the value of \(N\) for each query.

Output format

Print \(Q\) space-separated integers denoting the result for \(Q\) queries.

Constraints

\(1 \le N \le 10^9 \\ 1 \le P \le 10^6 \\ 1 \le Q \le 10^5\)