# Kbin

We call the k-binary number a natural number which has in its binary reprezentation exactly k
digits of 1. For example, the 23 is a 4-binary number because the binary reprezentation is 10111
and contains 4 digits of 1.

Given the N and k values, calculate the sum S of all k-binary numbers which are strictly lower than
N. Because the sum is very large, you have to calculate modulo 1234567.

### Input

The input contains the values N (2 ≤ N ≤ 10^{15}) and k (0 ≤ k ≤ 50) separated by a single space.

### Output

The output will contain the number S modulo 1234567.

### Constraints

Time limit: 1 second

Memory limit: 128 megabytes

### Examples

input 15 3 | output 45 |

Explanation of the first test:

1 – 1

2 – 10

3 – 11

4 – 100

5 – 101

6 – 110

7 – 111

8 – 1000

9 – 1001

10 – 1010

11 – 1011

12 – 1100

13 – 1101

14 – 1110

S=7+11+13+14=45