Lucky Tickets

题意翻译

一个 $n$ 位数,每位可以是给出的 $k$ 个数码中的一个数,可以有前导 $0$,输出前 $\frac n 2$ 位之和与后 $\frac 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 $ .