G. Lucky Ticketstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAll 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.InputThe 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.OutputPrint the number of lucky ticket numbers, taken modulo 998244353.ExamplesInput4 21 8Output6Input20 16Output1Input10 56 1 4 0 3Output569725Input1000 75 4 0 1 8 3 2Output460571165NoteIn 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.
Input4 21 8
Output6
['divide and conquer', 'dp', 'fft', '*2400']