POLSKI SPOJ

Dla danych liczb x, y oraz n wyznacz

czyli liczbę r taką, że 0 <= r < n oraz n | (x^y - r).

Wejście

t [liczba przypadków testowych <= 10]
x y n [2 <= x, n <= 2³⁰, 0 <= y <= 2³⁰ - łatwe (10¹⁰⁰⁰⁰ - trudne)

Pierwsze dwa testy są łatwe, kolejne cztery są trudne. Limit punktów (zadanie zostaje zaakceptowane) wynosi 2 pkt.

Wyjście

r [takie, że x^y = r (mod n)]

Przykład 1 (łatwy)

Wejście:
2
54015779 489100829 472960975
827371214 966345673 443599139

Wyjście:
350431544
391669493

Przykład 2 (trudny)

Wejście:
1
29809803 47901912849872523461864631327232122 1008098565

Wyjście:
718185534