Lucky Tickets

题意翻译

一个$n$位数，每位可以是给出的$k$个数码中的一个数，可以有前导$0$,输出前$n/2$位之和与后$n/2$位之和相等的方案数，保证$n$是偶数。 输入的第一行是两个整数$n,k$，接下来的一行有$k$个数$d_1,d_2,\cdots,d_k(0\leq d_i\leq 9)$ 输出一个数，为方案数模$998244353$的值

题目描述

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 $ .

输入输出样例

输入样例 #1

4 2
1 8

输出样例 #1

6

输入样例 #2

20 1
6

输出样例 #2

1

输入样例 #3

10 5
6 1 4 0 3

输出样例 #3

569725

输入样例 #4

1000 7
5 4 0 1 8 3 2

输出样例 #4

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 $ .