E. Mathlab
time limit per test
7 с
memory limit per test
512 megabytes
input
standard input
output
standard output

The function $$$f(x)$$$ is defined as the sum of all digits of $$$x$$$ in hexadecimal. Given an $$$n$$$-digit hexadecimal number $$$x$$$ and an index $$$k$$$, calculate $$$$$$\sum \limits_{i=0}^{x-1} f((16^k-1) \cdot i) \bmod 2^{64}.$$$$$$

Input

The first line contains two positive integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$ and $$$5k \ge n$$$).

The second line contains a string of length $$$n$$$ — the value of given $$$x$$$ in hexadecimal.

The string only consists of decimal digits and 'A','B','C','D','E','F'. Also the first digit is not '0'.

Output

The only line contains an integer — the answer.

Example
Input
4 1
7FFF
Output
1081320