Robot Upgrades

Time limit1sMemory limit2048 MB

Summary

Count the ways to set each of N parts to an upgrade level from 0 to M so that, for each i, at most A_i parts reach level i or higher, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

The Kingdom of ICPC is under attack by evil balloons! Fortunately, Morgan the robot is ready to defend the kingdom. To strengthen his power, there are $N$ parts, numbered from $1$ to $N$ , that can be upgraded. Each part can be upgraded between $0$ and $M$ times, inclusive.

To save resources, Morgan's upgrades are subject to $M$ restrictions, numbered from $1$ to $M$ . For restriction $i$ , the number of parts upgraded at least $i$ times must not exceed $A_i$ .

Adrian is planning which upgrades to apply to Morgan and wonders how many upgrade configurations satisfy all the restrictions. Two configurations are different if and only if at least one part has a different number of upgrades. Since the answer can be large, find it modulo $998\,244\,353$ .

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le 100\,000$ , $1 \le M \le 10$ ). The next line contains $M$ integers $A_1, A_2, \dots, A_M$ ( $1 \le A_i \le N$ ), given in non-increasing order, that is, $A_1 \ge A_2 \ge \dots \ge A_M$ .

Output

Output a single integer: the number of upgrade configurations that satisfy all restrictions, modulo $998\,244\,353$ .

Examples3

Example 1
Input
```
3 5
2 2 1 1 1
```
Expected output
```
64
```
Example 2
Input
```
1 2
1 1
```
Expected output
```
3
```
Example 3
Input
```
16 8
16 16 8 4 4 2 1 1
```
Expected output
```
720246211
```