In a sequence of numbers a₁, a₂, a₃, ... given the first term, and the rest are calculated using the formula:

a_i = (a_i-1)² mod 10000.

   Find the N-th term of the sequence.

Input                 

In the first row are the numbers a₁ and N, separated by a space. 0 ≤ a₁ ≤ 10000, 1 ≤ N ≤ 2000000010.

Output

Output a single number - a_N.

Samples