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:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Języki programowania:All

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