問題文

QUPC 2022 九州大学オンサイトには N 人の参加者がいます。i 番目の参加者の AtCoder のレーティングは A_i です。

N 人の参加者を以下の条件を満たすように、いくつかのチームに分けます。

• 各チームの人数は 1 人以上 3 人以下
• 各チームに所属する参加者の AtCoder のレーティングの平均値は K 以下
• AtCoder のレーティングの値に関わらず、1 人チームとして参加することは可能

条件を満たすチームの分け方は何通りあるかを求めてください。この問題の制約下で、答えは 10^{18} を超えないことが保証されています。

制約

• 1 \leq N \leq 18
• 0 \leq K \leq 4208
• 0 \leq A_i \leq 4208
• 入力は全て整数

入力例 1

3 2000
1999 2000 2001

出力例 1

4

3 人以下のチームの組み方は以下の 5 通りで、上の 4 通りが条件を満たします。

• 1 番目の参加者単独のチーム、2 番目の参加者単独のチーム、3 番目の参加者単独のチーム
• 1 番目の参加者と 2 番目の参加者と 3 番目の参加者の 3人チーム
• 1 番目の参加者と 2 番目の参加者の 2 人チーム、3 番目の参加者単独のチーム
• 1 番目の参加者と 3 番目の参加者の 2 人チーム、2 番目の参加者単独のチーム
• 2 番目の参加者と 3 番目の参加者の 2 人チーム、1 番目の参加者単独のチーム

入力例 2

4 2000
2500 3000 1000 2000

出力例 2

6

入力例 3

12 2000
3092 2432 2312 1867 1794 1730 1670 1523 1495 1299 1169 1024

出力例 3

297042