Dat je skup A koji sadrži n različitih prirodnih brojeva. Odrediti koliko ima podskupova skupa A za koje važi da je zbir najvećeg i najmanjeg elementa jednak datom broju m.

Ulaz.

(Ulazni podaci se nalaze u datoteci skupovi.in) U prvom redu se nalaze prirodni brojevi n i m (2 ≤ n ≤ 100.000, 1 ≤ m ≤ 1.000.000.000). U drugom redu se nalazi n različitih prirodnih brojeva, koji predstavljaju skup A.

Izlaz.

(Izlazne podatke upisati u datoteku skupovi.out) U prvom i jedinom redu treba ispisati ostatak pri deljenju broja podskupova kod kojih je zbir najvećeg i najmanjeg elementa jednak m i broja 1.000.000.007.

Primer 1.

5 9
7 2 9 5 4

5

6 11
2 4 6 8 10 12

0

Objašnjenje.

U prvom primeru traženi podskupovi su {2, 7}, {2, 4, 7}, {2, 5, 7}, {2, 4, 5, 7} i {4, 5}. Primetimo da skup {9} ne zadovoljava uslove zadatka, pošto je zbir najvećeg (broj 9) i najmanjeg (broj 9) elementa jednak 18. U drugom primeru ne postoji podskup kod koga je zbir najvećeg i najmanjeg elementa neparan broj, pa je zato rešenje 0.

#include <fstream>
#include <iostream>
#include <cstdlib>

#define MAXN 100001
#define MOD 1000000007

using namespace std;

long *a, *deg;
long n, m, sol;

void input()
{
  ifstream inFile;
  inFile.open("skupovi.in");
  inFile >> n >> m;
  a = new long [n];
  for (int i = 0; i < n; i++)
    inFile >> a [i];
  inFile.close();
}

int compare (const void *a, const void *b)
{
  return *(long *)a - *(long *)b;
}

void solve()
{
  qsort(a, n, sizeof(long), compare);
  deg = new long [n + 1];
  deg [0] = 1;
  for (int i = 1; i <= n; i++)
  {
    deg [i] = deg [i - 1] * 2;
    if (deg [i] > MOD)
      deg [i] -= MOD;
  }
  sol = 0;

  int left = 0;
  int right = n - 1;
  int count = 0;
  while (right > left)
  {
    if (a [left] + a [right] == m)
    {
      sol = sol + deg [right - left - 1];
      if (sol > MOD)
        sol -= MOD;
      count++;
    }
    if (a [left] + a [right] <= m)
      left++;
    else
      right--;
  }
  if (a [left] + a [right] == m)
  {
    count++;
    sol = sol + 1;
    if (sol > MOD)
      sol -= MOD;
  }
  cout << count << endl;
}

void output()
{
  ofstream outFile;
  outFile.open("skupovi.out");
  outFile << sol << endl;
  outFile.close();
}

int main()
{
  input();
  solve();
  output();
  check();
  return 0;
}