计数原理的简单方法（集合计数HihoCoder-1546计数）

给定一个包含N个整数的集合S={A1, A2, ... AN}，以及一个给定的整数K，请计算有多少个S的子集满足其中的最大值与最小值的和小于等于K。

例如对于S={4, 2, 5, 8}以及K=7,满足的条件的子集有以下4个:{2}, {2, 4}, {2, 5}, {2, 4, 5}。

Input

第一行包含两个整数N和K。

第二行包含N个整数A1, A2, ... AN。

对于30%的数据，1 <= N <= 20

对于70%的数据，1 <= N <= 1000

对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 1000000000, 0 <= K <= 2000000000, A1 ~ AN 两两不同。

Output

输出满足条件的子集数目。由于答案可能非常大，你只需要输出答案除以1000000007的余数。

Sample Input

Sample Output

题意：见题目描述

思路：这道题其实到现在我也没能理解，但是有两个结论先记下来：①：以第i个元素开头，第j个元素结尾的集合的个数为2^(j-i-1)个(最大小值必定位于集合内，大小位于两者之间的元素有j−i−1个，每个元素都有两种可能性，出现/不出现)。②：以第i个元素开头，第j以及所有x(i<x<j)结尾的集合共有2^（j-i）-1个。

举例说明以上两个结论: 集合 {1，2，3，4，5，6，7}

结论1：eg：i=2，j=5，集合有{2，5}、{2，3，5}、{2，4，5}、{2，3，4，5}共4个

结论2：eg：i=2，j=5，集合有{2，5}、{2，3，5}、{2，4，5}、{2，3，4，5}、{2，4}、{2，3，4}、{2，3}共7个