I. Strange Process
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given three arrays:

  • array $$$a$$$, initially consisting of $$$n$$$ ones;
  • array $$$b$$$, initially consisting of $$$m$$$ zeros;
  • array $$$c$$$, consisting of $$$m$$$ integers from $$$1$$$ to $$$50$$$.

We perform the following process on these arrays. The process consists of $$$m$$$ stages. During the $$$i$$$-th stage, the following occurs:

  1. first, for each element of the array $$$a$$$, one of three actions is independently chosen: it is multiplied by some prime number, divided by some prime number (it cannot be divided by a number that does not divide the element evenly), or remains unchanged. You don't have to choose the same action or prime number for each element of $$$a$$$;
  2. then you can either skip this step or choose any $$$k$$$ such that $$$a_k = c_i$$$, and assign $$$b_i = k$$$.

An array of $$$m$$$ numbers from $$$0$$$ to $$$n$$$ is called achievable if it can be obtained as a result of this process as the array $$$b$$$.

Your task is to count the number of achievable arrays.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^4$$$).

The second line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le 50$$$).

Output

Print one integer — the number of achievable arrays, taken modulo $$$998244353$$$.

Examples
Input
4 3
4 2 3
Output
21
Input
2 4
1 2 3 4
Output
51
Input
1 2
47 34
Output
3