Problem Background

You actually made it through, that's incredible, isn't it?

The process of striving is quite interesting.

Well,

What are you waiting for?

Problem Description

Madeline has distributed the strawberries she collected among her friends.

The alternating red and golden strawberries are very popular among her friends.

To thank Madeline, her friends have collected many colorful beads, planning to string them into a colorful necklace for her.

After careful preparation by her friends, there are now $n$ beads on the table, in $k$ different colors. Specifically, there are $a_i$ beads of the $i$-th color.

Looking at the crystal-clear beads on the table, her friends are now puzzled because they don't know how to string them together to make the most beautiful necklace.

Her friends have asked for your help to find out the total number of distinct schemes.

Her friends cannot distinguish the order of the beads, so two beads are different only if their colors are different.

The necklace must be complete, so all beads form a connected block.

The necklace also cannot be too chaotic, so all beads must form a pseudoforest.

After multiple inquiries from Madeline's friends, you found that two subtrees of this pseudoforest are different only if their corresponding points have different colors or the two subtrees are not isomorphic. The order of different subtrees matters.

For example, the following partial necklace arrangements are all distinct:

Her friends are in a hurry, so if two necklaces can achieve the same result by rotating the base ring, then these two necklaces are essentially the same.

Input Format

The first line contains two integers $n$ and $k$, representing the total number of beads and the number of different colors, respectively.

The next line contains $k$ integers $a_i$, representing the number of beads of each color.

Output Format

Output an integer representing the number of schemes modulo $998244353$.

Sample Input and Output

Sample Input #1

3 3
1 1 1

Sample Output #1

8

Sample Input #2

4 2
1 3

Sample Output #2

15

Notes

Pseudoforest: A connected graph with $n$ vertices and $n$ edges, without self-loops. It is easy to see that such a graph consists of a ring with some trees attached to it.

Base ring: The ring in the pseudoforest.

For $5\%$ of the data, $n \leq 8$.

For another $10\%$ of the data, $k = 1, n \leq 10^3$.

For the first $30\%$ of the data, $n \leq 10^3$.

For another $20\%$ of the data, $k = 1, n \leq 5 \times 10^4$.

For the first $80\%$ of the data, $n \leq 5 \times 10^4$.

For $100\%$ of the data, $a_i > 0, \sum a_i = n, n \leq 2 \times 10^5, k \leq n$.

Explanation of the second sample:

There are $15$ possible cases:

见题面 Input 部分

见题面 Output 部分