Summing Sequence (8 Points)

Problem Statement

You have an array $a$ of $n$ non-negative integers. You wish to decrease some (any number) of the integers so that they remain non-negative and the sum of the sequence is equal to $k$. In other words, you can form a new sequence $b$ of length $n$ such that $0 \leq b_i \leq a_i$ and $\sum_{x\in b} x = k$.

Determine the number of distinct ways to do this modulo $998244353$. We call two ways distinct if the resulting sequences after decreasing some of the integers have a different number at some index.

Input Format

Your first line will contain two integers $n$ and $k$. Your next line will contain $n$ space-separated integers representing $a$.

Output Format

Output a single integer representing the number of ways modulo $998244353$.

Constraints

• $1 \leq n, k \leq 3 \cdot 10^4$
• $1 \leq a_i \leq 15$

Sample Cases

4 3
1 1 1 1

4

Explanation 1

The different sequences you can make are $[0,1,1,1]$, $[1,0,1,1]$, $[1,1,0,1]$ and $[1,1,1,0]$.

3 28
10 10 10

6

Explanation 2

There are 3 ways if you decrease one of the 10s to an 8, 3 ways where you decrease 2 of the 10s to 9s.

15 33 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

509689781

Explanation 3

Remember to modulo by $998244353$.