#6502. 「雅礼集训 2018 Day4」Divide

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

第一,生存是文明的第一需要;第二,文明不断增长和扩张,但宇宙中的物质总量保持不变。——叶文洁

危机纪元 205 年。

经历过惨绝人寰的大低谷后,人类,又一次站了起来,全面解放实现技术暴涨,进入全息社会阶段,并建立起了庞大的宇宙舰队。

今天对于三大舰队而言,又是一如既往的军事演练。

共有 n 艘飞船参与演练,每艘飞船都有一个武力值 w_i

你需要把它们分成两队: A 队与 B 队,每队飞船数目任意。

我们发现,如果两艘飞船 i j 的武力值相加不小于 m 且不在同一队,那么这两艘飞船就能配合默契。

请问最多能有多少对飞船配合默契,同时还需算出有多少种分队方案可以达到此效果。

输入格式

第一行两个正整数 n, m

第二行 n 个自然数,第 i 个表示 w_i

输出格式

一行两个整数,用空格隔开,分别表示最多的配合默契对数与可以达到此效果的方案数,方案数对 10^9 + 7 取模。

样例

样例输入 1

2 10
5 5

样例输出 1

1 2

数据范围与提示

对于全部数据, n \leq 2000, m \leq 2×10^6, w_i \leq 10^6

  • 存在 30 \% 的数据满足 n \leq 18
  • 另有 20 \% 的数据满足 w_i 排序后是等差数列