Kam is a series of a very challenging problems.Here we begin with kam1 the easiest one.Given number N of at most 18 digit and  M .output the result of the following:

For number consists of  n digits from d[0],...,d[n-1]

result = sum(d[0]^M %(4*10^8)+..+d[(n/2)-1]^M%(4*10^8))*sum(d[n/2]^M %(4*10^8)+..+d[n-1]^M%(4*10^8))

N will guarantee to have even number of digits

Input

2 numbers N and M where N will be a number of at most 18 digits and M will be between 0<=M<=1000000000

Output

The same as problem said

print endl after test cases

Example

Input:
22 2

Output:
16