問題一覧 > 通常問題

No.794 チーム戦 (2)

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : ei1333333ei1333333 / テスター : treeonetreeone
9 ProblemId : 2217 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-03-26 21:17:58

問題文

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。