przekręcanie się long longów

Mam takie zadanie

http://solve.edu.pl/contests​/download_desc/2213
i taki kod:
https://wandbox.org/permlink​/XozBh83LBn7Hp3oG

Na dwóch testach pokazuje mi błędą odpowiedź. Prawdopodobnie przekręcają się long longi przy mnożeniu w funkcji szybkiego potęgowania.
Pomyślałem o użyciu algorytmu mnożenia rosyjskich chłopów.
To jest prawie taka sama funkcja jak ta którą mam do szybkiego potęgowania, tylko mnożenie trzeba zamienić na dodawanie i...za cholerę mi to nie wychodzi :-(
Ktoś pomoże?

Algorytm jest błędny, ale nie ze względu na long longi (tym bardziej, że działasz na modulo). Według twojego programu 625000450000081 jest liczbą pierwszą. A tak na prawdę jest to liczba złożona, która mieści się w zakresie 10^17 (tym bardziej w long longu, o ile jest 64 bit). Dowód na złożoność: Czynniki liczby 625000450000081.