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.
skupovi.in
|
|
skupovi.out
|
5 9
7 2 9 5 4
|
|
5
|
Primer 2.
skupovi.in
|
|
skupovi.out
|
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.