Skupovi
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.
Input U prvom redu standardnog ulaza 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.
OutputU prvom i jedinom redu standardnog izlaza 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.
Ulaz:
5 9
7 2 9 5 4
Izlaz:
5Primer 2.
Ulaz
6 11
2 4 6 8 10 12
Izlaz
0Objaš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.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.