1794: 快速求幂

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：76 Solved：20

Description

       张老师今天要你求 ( a ^k ) mod 1000 的值 ， k是正整数，也就是求 a值 k 正整数次幂后1000的余数。他给的数字很大，还要求你能快速求解出结果。

Input

一行输入两个长正整数 a 与 k。空格分隔。

Output

一个正整数 a^k  mod 1000 的值。

Sample Input Copy 

7 999

Sample Output Copy 

143

HINT

  0<a,k<2^31