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.|

LETTERS5 - Listy i koperty 1 i pół

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:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.