POLSKI SPOJ

Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Zadanie w systemie SPOJ (trudne)

11350. Listy i koperty 1 i pół

Kod zadania: LETTERS5

Jaś nadal pracuje na poczcie. Jego szef wymyślił nowy problem podobny do tego, co za pierwszym razem. Znów napisano n listów i zaadresowano dla nich n kopert. Szefa interesuje tym razem to, na ile sposobów można włożyć listy do kopert tak, aby dokładnie k listów trafiło do właściwych kopert. Ponieważ ta szukana liczba może być bardzo duża, należy ją podać modulo p (gdzie p to pewna dana liczba pierwsza).

Wejście

Pierwsza linia zawiera dwie liczby całkowite: liczbę testów t (t≤20000) oraz liczbę pierwszą p (p<1000).

W kolejnych t liniach znajdują się po dwie liczby całkowite n i k. Pierwsza z nich to liczba wszystkich listów (i jednocześnie kopert), druga - liczba listów, które mają trafić do właściwych kopert. Zachodzi: 0≤kn≤2*1018.

Wyjście

Dla każdego przypadku testowego, w osobnej linii, jedna liczba całkowita, oznaczająca na ile sposobów (modulo p) można włożyć listy do kopert, zgodnie z życzeniem szefa.

Przykład

Wejście:
4 5
0 0
3 1
4 2
5 4


Wyjście:
1
3
1
0

Dodane przez:Witold Długosz
Data dodania:2012-04-09
Limit czasu wykonania programu:0.200s
Limit długości kodu źródłowego50000B
Limit pamięci:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Języki programowania:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.