Elevar un número a otro (cuando ambos son números enteros) se puede hacer de forma recurrente de la siguiente forma:
| x0 | = | 1 |
| xn+1 | = | x ∗ xn |
Hoy nos pedirán elevar números muy grandes, por lo que:
De esta forma, la recurrencia anterior queda:
xn+1 mod k = ((x mod k) ∗ (xn mod k)) mod k
Cada caso de prueba consiste en una única línea de dos números enteros no negativos, x y n. Se garantiza que los números no serán mayores que 231−1.
La entrada terminará cuando ambos números sean cero; ese caso no generará salida.
Para cada caso de prueba se escribirá una línea que contendrá el resultado de elevar ambos números, módulo 31.543.
2 5 31542 1 31543 1 1000000 5 0 0
32 31542 0 31429