Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

divide and conquer

dp

fft

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Lucky Tickets

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Input

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.

Output

Print the number of lucky ticket numbers, taken modulo $$$998244353$$$.

Examples

Input

4 2

1 8

Output

6

Input

20 1

6

Output

1

Input

10 5

6 1 4 0 3

Output

569725

Input

1000 7

5 4 0 1 8 3 2

Output

460571165

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 17:47:26 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|