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$$$.
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.
Print the number of lucky ticket numbers, taken modulo $$$998244353$$$.
4 2
1 8
6
20 1
6
1
10 5
6 1 4 0 3
569725
1000 7
5 4 0 1 8 3 2
460571165
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$$$.
Name |
---|