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¹⁵) 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