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

Input 1

4 3
1 1 1 1

Output 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]~.

Input 2

3 28
10 10 10

Output 2

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.

Input 3

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

Output 3

509689781

Explanation 3

Remember to modulo by ~998244353~.