Vé cân bằng

Một vé là một dãy gồm $n$ chữ số lấy từ tập được phép; chữ số đầu tiên có thể bằng $0$ . Vé được gọi là cân bằng khi tổng của $n /2$ vị trí đầu bằng tổng của $n /2$ vị trí cuối. Hãy đếm số vé cân bằng.

Input

Dòng đầu chứa độ dài chẵn $n$ và số chữ số được phép $k$ .
Dòng thứ hai chứa $k$ chữ số phân biệt.

Output

In số vé cân bằng modulo $998244353$ .

Constraints

$2 \leq n \leq 1 0^{5}$ và $n$ chẵn.
$1 \leq k \leq 10$ ; các chữ số được phép phân biệt và thuộc $[0, 9]$ .

Scoring

Subtask $1$ ( $50$ điểm): Đại lượng $n$ không vượt $2000$ .
Subtask $2$ ( $50$ điểm): Không có ràng buộc bổ sung.

Example

Test 1

Input

4 2
0 1

Output

Giải thích: Ta xét mọi nửa vé có thể tạo, đếm theo tổng chữ số rồi ghép hai nửa có cùng tổng; tổng số cặp là kết quả.

Lời giải tóm tắt

Thuật toán: Đặt P[d]=1 cho chữ số được phép. Tính R=P^(n/2). Khi đó R[s] là số nửa vé có tổng s. Hai nửa độc lập và phải có cùng tổng, nên đáp án là sum_s R[s]^2. Mọi phép tính modulo 998244353.
Chứng minh đúng: Khai triển tích P^(n/2) chọn một đơn thức từ mỗi thừa số, tương ứng chọn một chữ số tại mỗi vị trí; số mũ là tổng chữ số. Với tổng s, có R[s] cách cho mỗi nửa, nên có R[s]^2 cặp. Các tổng khác nhau rời nhau.
Độ phức tạp: O(L log L log n) thời gian, O(L) bộ nhớ, L<=9n/2+1.