Last Three Digits of Exponentiation

Given two integers a and b, compute the last three digits of \(a^b\). If a^b has fewer than three digits, prepend the result with leading zeros so that the output always contains exactly three digits.

You can assume that a and b are non-negative integers and that b might be large so that a direct computation of a^b is not feasible. Use modular exponentiation with modulus \(1000\) to solve this problem efficiently.

inputFormat

The input consists of a single line containing two space-separated integers a and b.

outputFormat

Output the last three digits of \(a^b\) as a three-digit number (with leading zeros if necessary).

sample

2 3

008