Problem description

Jedną z potencjalnych metod złamania protokół bezpiecznej wymiany klucza Diffiego-Hellmana jest rozwiązanie problemu logarytmu dyskretnego. Dla danych liczb a, b, p (p jest pierwsze), należy wyznaczyć wykładnik x, że: a^x ≡ b (mod  p)

Celem tego zadania nie jest rozwiązanie tego problemu wydajnie (na tyle by zagrozić bezpieczeństwu protokołu Diffiego-Hellmana), ale wystarczająco wydajnie, żeby dostać akcepted na wszystkich testach.

Napisz program, który: wczyta liczby a, b, p, wyznaczy najmniejsze x, że a^x daje resztę b przy dzieleniu przez p.

Wejście

W pierwszym (i jedynym) wierszu wejścia znajdują się trzy liczby całkowite: a, b, p, pooddzielane pojedynczymi odstępami.

Wyjście

Wyjściem powinna być jedna liczba całkowita – najmniejsze nieujemne rozwiązanie podanego na wejściu problemu logarytmu dyskretnego.

Jeśli zadany problem nie ma rozwiązania – należy wypisać jedno słowo NIE.

Ograniczenia

1 ≤ a ≤ 10⁹, 0 ≤ b ≤ p ≤ 10⁹, p jest liczbą pierwszą.

Przykład

4 10 13

5

2 6 13

5