Given number A and number B, calculate pow( A, B ) modulo 100007.

Input data specification
The only line of input contains two integer numbers: A and B.
1 <= A <= 1 000 000 000
0 <= B <= 1 000 000 000

Output data specification
The only line of output should contain resulting value.

Sample input
12 6

Sample output
85781

Note
12^6 = 2,985,984;
2,985,984 % 100007 = 85,781.