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$