Divisibility by 2^N

Consider an infinite numerical sequence defined as follows: (A_1 = 1), (A_2 = 12), ..., (A_10 = 12345678910), (A_11 = 1234567891011), and so on. The first term is (1), and each subsequent term is formed by appending the decimal representation of its index to the end of the previous term's decimal value.

Given two integers, (M) and (N), your task is to find how many terms in this sequence, with an index not exceeding (M), are divisible by (2^N) without a remainder.

Input

The input consists of a single line containing two positive integers, (M) and (N) ((0 < M $\le$ 10^18), (0 < N < 7)).

Output

Output a single line containing the answer to the problem.

Examples