Elévame
Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
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:
- Tendremos que hacerlo lo más rápido posible.
- Para evitar el desbordamiento del valor devuelto, en vez del número final exacto, restringiremos el resultado a un intervalo [0..k−1], siendo k la constante 31.543.
De esta forma, la recurrencia anterior queda:
xn+1 mod k = ((x mod k) ∗ (xn mod k)) mod k
Entrada
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.
Salida
Para cada caso de prueba se escribirá una línea que contendrá el resultado de elevar ambos números, módulo 31.543.
Entrada de ejemplo
2 5 31542 1 31543 1 1000000 5 0 0
Salida de ejemplo
32 31542 0 31429