点击此处下载样例文件

题目描述

有 n 头牛，第 i 头牛的好斗值为 $a_i$。

现在要把它们分成两队：A 队与 B 队。

如果不在同一队中的两头牛的好斗值之和不小于 m ，那么它们俩就可以进行 PK。

问：

（1）最多能有多少对牛可以进行 PK？

（2）在满足最多对牛可以进行 PK 的前提下，共有多少种分队方案？

输入格式

第一行：两个整数 n, m。

第二行：n 个整数 $a_i$。

输出格式

一行两个整数，用一个空格隔开，分别表示可以进行 PK 的最多对数与满足条件的方案数（方案数对 $10^9 + 7$ 取模）。

样例输入

4 6
1 2 3 4

样例输出

2 4

样例解释

最多 2 对牛可以 PK。划分方案有 4 种：

（1）第 1, 2, 3 头牛在 A 队，第 4 头牛在 B 队。此时第 2 头牛和第 4 头牛可以 PK，第 3 头牛和第 4 头牛可以 PK。

（2）第 1, 2, 3 头牛在 B 队，第 4 头牛在 A 队。PK 情况同上。

（3）第 1, 4 头牛在 A 队，第 2, 3 头牛在 B 队。PK 情况同上。

（4）第 1, 4 头牛在 B 队，第 2, 3 头牛在 A 队。PK 情况同上。

数据范围

对于全部数据，$n ≤ 2000, m ≤ 2×10^6, a_i ≤ 10^6$。

存在 30% 的数据满足 $n ≤ 18$

另有 20% 的数据满足 $a_i$ 排序后是等差数列