/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
魔法使いのすぬけ君は 1 から N の番号がついた N 個の魔法のランプを持っています。 i 番目のランプのコストは a_i です。 はじめ、どのランプも灯っていません。
すぬけ君はMPという整数値を持っており、はじめは X です。 すぬけ君がコスト x のランプを灯すとMPが x だけ減少します。 すぬけ君が 1 つランプを灯すごとに、コストが 1 以上であるすべてのランプについてコストが 1 小さくなります。
ランプを灯す順序は N! 通りありますが、このうちMPが 0 未満になることがないような場合の数を 998244353 で割ったあまりを求めてください。
制約
- 1 \le N \le 100
- 0 \le a_i \le 10^{9}
- 0 \le X \le 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X a_1 a_2 \dots a_N
出力
答えを出力してください。
入力例 1
3 1 0 1 2
出力例 1
3
MPが 0 未満になることがない順序の一例を説明します。
- はじめに 1 番のランプを灯します。MPが 0 だけ減少します。
- 次に 3 番のランプを灯します。MPが 1 だけ減少します。
- 最後に 2 番のランプを灯します。MPが 0 だけ減少します。
ランプのコストが 0 未満にならないことに注意してください。
入力例 2
6 8 2 1 4 8 1 4
出力例 2
176
入力例 3
20 50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
出力例 3
63942667
998244353 で割ったあまりを求めることを忘れずに。
Score : 800 points
Problem Statement
Snuke the wizard has N magical lamps numbered 1 to N. The cost of the i-th lamp is a_i. Initially, none of the lamps are lit.
Snuke has an integer value called MP, which is initially X. When Snuke lights a lamp with cost x, his MP decreases by x. Each time Snuke lights one lamp, the cost of all lamps with cost at least 1 decreases by 1.
There are N! possible orders to light the lamps. Find the number, modulo 998244353, of such orders where MP never becomes negative.
Constraints
- 1 \le N \le 100
- 0 \le a_i \le 10^{9}
- 0 \le X \le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X a_1 a_2 \dots a_N
Output
Print the answer.
Sample Input 1
3 1 0 1 2
Sample Output 1
3
We explain one order where MP never becomes negative.
- First, light lamp 1. MP decreases by 0.
- Next, light lamp 3. MP decreases by 1.
- Finally, light lamp 2. MP decreases by 0.
Note that the cost of a lamp never becomes negative.
Sample Input 2
6 8 2 1 4 8 1 4
Sample Output 2
176
Sample Input 3
20 50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Sample Output 3
63942667
Do not forget to find the remainder modulo 998244353.