Skupovi
Set A that consists of n different natural numbers is given. Determine the number of subsets of set A for which applies that the sum of the largest and the smallest element is equal with given number m.
InputIn the first row there are natural numbers n and m (2 ≤ n ≤ 100.000, 1 ≤ m ≤ 1.000.000.000). In the second row there is n different natural numbers, that represent set A.
OutputIn the first and only row write the modulus of the division of the number of subsets that has sum of the largest and smallest numbers equal to m and the number 1.000.000.007.
Example 1
Input:
5 9
7 2 9 5 4
Output:
5Example 2
Input:
6 11
2 4 6 8 10 12
Output:
0Explanation,
In the first test example the required subsets are {2, 7}, {2, 4, 7}, {2, 5, 7}, {2, 4, 5, 7} i {4, 5}. Notice that set {9} does not fulfill the task limitation, since the sum of the largest (number 9) and the smallest (number 9) element equals 18. In the second test example there isn't a subset such that the sum of the largest and the smallest element is an odd number, so the result is 0.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.