Write a polyglot that compiles / runs in as many of the following languages as possible:

1[bash, zig, C, elixir, erlang, fish, golfscript, haskell, J, java, julia, lua, odin, perl, python 0, scheme, rust, typescript, whitespace]

(for exact versions / compilers / docker images, a sample runner is attached below). In each language, the program should:

Input

The first line contains $a$ ($2^8 \leq a < 2^{16}$).

The second line contains $b$ ($2^6 \leq b < 2^8$).

The third line contains $c$ ($2^{10} \leq c < 2^{12}$).

Output

Output a single integer equal to $a^b \mod c$.

pickelang is an esolang that uses the stack-based pickle virtual machine for evaluation; turing completeness is achieved by recursive pickle functionality using the BINPERSID opcode, add, and getitem functions (a sample runner is attached below).

Submit the shortest pickelang payload that passes 5 test cases specified below (100s timeout, 100MB memory limit).

struct.pack and struct.unpack are given for convenience.

Input

The input is a single string in the format [A, B, C] ($2 \leq A < 2^{15}, 1 \leq B < 2^{15}, 2^{15} \leq C < 2^{16}$) and can be retrieved using the input function.

Output

Output a single integer equal to $A^B \mod C$. This can be done by stopping the outermost unpickler evaluation with $A^B \mod C$ on the top of the stack.

Write the shortest Brainfuck program that computes powmod as specified (a sample runner is attached below).

Note: You are in charge of converting strings to ints and ints to strings. Don’t be lazy now.

Input

The first line contains $a$ ($10 \leq a \leq 999$).

The second line contains $b$ ($50 \leq b \leq 100$).

The third line contains $c$ ($100 \leq c \leq 999$).

Output

Output a single integer equal to $a^b \mod c$.