Problema número 295

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=xxn

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