Kam is a series of a very challenging problems. Here we begin with kam1 the easiest one. Given number N of at most 18 digits 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⁸) + ... + d[(n/2)-1]^M % (4 × 10⁸)) × sum(d[n/2]^M % (4 × 10⁸) + ... + d[n-1]^M % (4 × 10⁸))

N will guaranteed to have an 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 a new line after each test case.

Example

Input:
22 2

Output:
16