Your execution algo works an order of n shares across m venues during one session. Venue i can fill at most c_i shares. Fills arrive one share at a time, but the venue a fill came from is not observable until the session ends, so the only thing the session can end with is the final allocation: how many shares each venue filled.

Count the possible final allocations: vectors (x_1, ..., x_m) of non-negative integers with x_1 + ... + x_m = n and x_i <= c_i for every venue. Since the count can be enormous, output it modulo 998244353.

Input

The first line contains n and m. The second line contains c_1 ... c_m.

Output

One integer: the number of possible allocations, modulo 998244353. If the order cannot be fully filled, output 0.

Constraints

0 <= n <= 10^9

1 <= m <= 16

0 <= c_i <= 10^9

Scoring

This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.