Calcula \(a^b \bmod 1337\), donde \(b\) es un entero positivo enorme dado por sus dígitos decimales.

Entrada

La primera línea tiene \(a\) \((1 \le a \le 2^{31} - 1)\) y la cantidad de dígitos \(k\) \((1 \le k \le 2000)\) de \(b\). La segunda tiene los \(k\) dígitos de \(b\), del más significativo al menos significativo, sin ceros a la izquierda.

Salida

El valor de \(a^b \bmod 1337\).

Ejemplo 1

Entrada

2 1
3

Salida

8

Ejemplo 2

Entrada

2 2
1 0

Salida

1024

Ejemplo 3

Entrada

1 4
4 3 3 8

Salida

1

Ejemplo 4

Entrada

2147483647 3
2 0 0

Salida

1198