No.794 チーム戦 (2)

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 71
作問者 : ei1333ei1333 / テスター : treeonetreeone
7 ProblemId : 2217 / 出題時の順位表

問題文

yukicoder コンテストオンサイトには $N$ 人の参加者がいます。$i$ 番目の人のレートは $A_i$ です。

これからすべての人は $2$ 人 $1$ 組のチームを組みます。ただしそれぞれのチームのレートの和は $K$ 以下にする必要があります。 同じ人が複数のチームに所属することはできません。

このようなチームの組み方は何通りあるか、 $10^9+7$ で割った余りで求めてください。

入力

入力は以下の形式で標準入力から与えられます。

$N$ $K$
$A_1$ $A_2$ $...$ $A_N$
  • $2 \le N \le 2 \times 10^5$, $N$ は偶数
  • $1 \le K \le 2 \times 10^9$
  • $1 \le A_i \le 10^9$
  • 入力は全て整数

出力

$1$ 行に、チームの組み方を $10^9+7$ で割った余りで出力してください。

サンプル

サンプル1
入力
4 6
2 3 1 4
出力
2

以下の $2$ 通りのチームの組み方があります。

  1. $1$ 番目と $2$ 番目, $3$ 番目と $4$ 番目
  2. $1$ 番目と $4$ 番目, $2$ 番目と $3$ 番目
サンプル2
入力
6 100
1 3 3 3 3 3
出力
15
サンプル3
入力
2 1
1 1
出力
0
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。