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

Advertisement blocking software were detected ;( Please add this webpage to whitelist.

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.