Potências Cíclicas Modulares

#154
Made by: Crazynds
256MB
1s

Você recebeu três números inteiros positivos $X$, $P$ e $M$. Seu objetivo é calcular:

$$ [ R = X^P \bmod M ] $$

onde a operação ^ representa potenciação.

Entretanto, como $P$ pode ser muito grande, calcular $X^P$ diretamente é inviável. Você deve encontrar uma forma eficiente de obter o resultado sem overflow e sem multiplicações desnecessárias.

Além de determinar o resultado final R, você também deve identificar o ciclo da sequência de potências modulares.

Detalhes

Defina a sequência: $$ [ A_0 = 1, \quad A_i = (A_{i-1} \times X) \bmod M ] $$

Essa sequência é cíclica, pois existem apenas $M$ valores possíveis ($0..M-1$).

Você deve descobrir:

  1. O primeiro elemento do ciclo;
  2. O tamanho do ciclo;
  3. O valor final $R = X^P mod M$.

Input

A primeira linha contém um inteiro $T$ representando o número de casos de testes. $(1 ≤ T ≤ 10^4)$

Cada caso de teste contém três inteiros:

X P M
  • $1 ≤ X ≤ 10^8$
  • $1 ≤ P ≤ 10^{18}$
  • $2 ≤ M ≤ 10^6$

A somatório dos $M$ de todos os casos de testes não passam de $2*10^7$.

Output

Imprima três inteiros separados por espaço:

vIni tamCliclo R

onde:

  • $vIni$ é o primeiro valor do ciclo (valor em que a sequência começa a repetir);
  • $tamCliclo$ é o número de valores distintos no ciclo;
  • $R$ é o valor de $X^P mod M$.
Input Example
Output Example 
10
8 72 10
10 50 10
9 68 6
10 21 25
6 84 24
1 43 20
8 1 11
5 18 7
1 28 5
6 23 13

8 4 6
0 1 0
3 1 3
0 1 0
0 1 0
1 1 1
1 10 8
1 6 1
1 1 1
1 12 11

10
10 49 4
5 63 4
2 6 23
3 44 7
2 97 12
7 44 27
9 78 24
7 89 9
1 3 8
6 87 26

0 1 0
1 1 1
1 11 18
1 6 2
4 2 8
1 9 4
9 1 9
1 3 4
1 1 1
6 12 8