Zadanie ASD12
Treść
Basia wybierała się na wycieczkę. W tym celu postanowiła się spakować. Zaczęła wkładać do plecaka wszystkie rzeczy, które zaplanowała ze sobą zabrać. Niestety okazało się, że jej rzeczy nie mieszczą się w plecaku. Biedna nie wiedziała co ze sobą zrobić. Na szczęście ma znajomego informatyka, którego poprosiła o pomoc.
Ale co informatyk mógł poradzić? No nic. W końcu jeśli rzeczy się nie mieszczą, to się nie mieszczą. Postanowili z Basią, że spakują do plecaka tyle rzeczy, ile tylko się da, a resztę Basia zostawi w domu. Niestety teraz jest kłopot, które rzecz wybrać.
Zadanie
Wylicz dla Basi, znając dokładne rozmiary rzeczy Basi oraz rozmiar plecaka, na ile sposobów może spakować plecak w taki sposób, żeby był on całkowicie wypełniony. Basia pomogła Ci o tyle, że poukłada swoje rzeczy po kolei według rozmiarów od najmniejszego do największego.
Specyfikacja wejścia
W pierwszej linii wejścia znajduje się liczba naturalna d (1 <= d <= 100), określająca liczbę zestawów danych, które za chwilę pojawią się na wejściu. Opis pojedynczego zestawu składa się z dwóch linii. W pierwszej znajdują się dwie liczby N i M (1 <= N <= 1.000.000.000, 1 <= M <= 32)określającej odpowiednio rozmiar plecaka oraz liczbę rzeczy, które Basia chce w niego spakować. W drugiej linii znajduje się M liczb oddzielonych spacją, które są posortowane rosnąco (wszystkie są różne, każda z nich jest liczbą dodatnią, nie większą niż 1.000.000).
Specyfikacja wyjścia
Dla każdego zestawu na wejściu należy wypisać jedną liczbę na wyjściu oznaczającą liczbę sposobów, w jaki można całkowicie spakować plecak Basi używając jej rzeczy.
Przykład
Wejście
2
5 5
2 3 4 5 6
10 6
1 2 3 4 5 6
Wyjście
2
5