G. Lucky Tickets
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

All bus tickets in Berland have their numbers. A number consists of $n$ digits ($n$ is even). Only $k$ decimal digits $d_1, d_2, \dots, d_k$ can be used to form ticket numbers. If $0$ is among these digits, then numbers may have leading zeroes. For example, if $n = 4$ and only digits $0$ and $4$ can be used, then $0000$, $4004$, $4440$ are valid ticket numbers, and $0002$, $00$, $44443$ are not.

A ticket is lucky if the sum of first $n / 2$ digits is equal to the sum of remaining $n / 2$ digits.

Calculate the number of different lucky tickets in Berland. Since the answer may be big, print it modulo $998244353$.

Input

The first line contains two integers $n$ and $k$ $(2 \le n \le 2 \cdot 10^5, 1 \le k \le 10)$ — the number of digits in each ticket number, and the number of different decimal digits that may be used. $n$ is even.

The second line contains a sequence of pairwise distinct integers $d_1, d_2, \dots, d_k$ $(0 \le d_i \le 9)$ — the digits that may be used in ticket numbers. The digits are given in arbitrary order.

Output

Print the number of lucky ticket numbers, taken modulo $998244353$.

Examples
Input
4 21 8
Output
6
Input
20 16
Output
1
Input
10 56 1 4 0 3
Output
569725
Input
1000 75 4 0 1 8 3 2
Output
460571165
Note

In the first example there are $6$ lucky ticket numbers: $1111$, $1818$, $1881$, $8118$, $8181$ and $8888$.

There is only one ticket number in the second example, it consists of $20$ digits $6$. This ticket number is lucky, so the answer is $1$.