URI Online Judge | 2711

Unlocking a Cell Phone

By Diego Rangel, FACIT BR Brazil

Timelimit: 2

During cryptography class, Rangel is bored.

-Gu, hey, Gu! - Rangel calls his friend.

-Hey, man! - Gustavo replies.

-Can I borrow your phone? - Rangel says hopefully.

-No way, you are going to comment my social media posts – says Gustavo.

-Ok – Rangel replies sadly.

Gustavo is a nice guy and does not want to see his friend sad. Considering that in his mind, he calls Vânia and they both come up with a challenge to get rid of Rangel's boredness and make him like cryptography.

-Let's go Rangel, we challenge you! - say Gustavo and Vãnia, both smiling.

-Challenge? What kind of challenge? - says Rangel.

-Don't you want to use my phone? Come on, we have a challenge for you. Do you accept it? - they ask him.

-Yes, let's do it! - says Rangel, even more curious.

- OK, we are going to explain it:

We are going to change the password of my phone, and you have to find out what it is. It is not going to be an easy task. We will give you three numbers B, N and M, and we want you to find out the fourth number. This number will be my password! However, do not think this is going to be easy, because to discover the fourth number you need to solve the following equation:

BE = N mod M

Simple, right? We are interested that you discover the value of E, we assure you that the value of E is between [0, M - 1] and M is a prime number! Hahaha - Come on, you need to be fast! Well, you only have class time to solve!

-Ok, I'll take it, but I will use my laptop to help me – says Rangel cheerfully.

-Ok, show me what you can do. - say Gustavo and Vânia.

-I am going to give you a clue. Remember, Rangel, the value is between [0,M -1], but if it is not, it is -1!

Rangel is ready to take the challenge and decided to use programming to help him out. He asked your help to develop the code. Are you going to turn down this challenge?

Input

There are several case tests. Each case consists of three integers B, N, M where B and N (0 < B, N < 105) and M are a prime number.

Output

For each case, you will have to print the value for E, and if this value does not follow the following property [0, M - 1], you wll have to print -1. Let's go, help Rangel!

Input Sample Output Sample

2 64 107

5 15625 18047

5 1458 107

77 12 19

1 1 3

6

6

27

-1

0