Xét các số nguyên dương có đúng ~k~ bit ~1~ trong phân tích nhị phân. Gọi các số đó là các số thuộc lớp ~k.~ Ví dụ: ~23_{10} = 10111_2~ là một số thuộc lớp ~4.~

Cho hai số nguyên ~n~ và ~k~ hãy tính tổng các số nhỏ hơn ~n~ và thuộc lớp ~k.~

Input

Gồm một dòng duy nhất chứa hai số nguyên ~n(2≤n≤10^{15})~ và ~k(0≤k≤50).~

Output

Gồm một số nguyên duy nhất là kết quả của bài toán theo modulo ~1234567.~

Example

Input

15 3

Output

45