Numim număr k-binar un număr natural care în scrierea sa în baza 2 are exact k cifre de 1. De exemplu numărul 23 este 4-binar pentru că el se scrie în baza 2 sub forma 10111 și conține exact patru biți de 1.

Cerința

Pentru valorile date ale lui N și k, să se calculeze suma tuturor numerelor k-binare strict mai mici decât N. Deoarece sumele sunt foarte mari, acestea vor fi calculate modulo 1234567.

Date de intrare

Fișierul de intrare kbin.in conține pe prima linie valorile N şi k separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire kbin.out va conţine pe prima linie un singur număr natural s reprezentând suma cerută modulo 1234567.

Restricții și precizări

• 2 ≤ N ≤ 1015
• 0 ≤ k ≤ 50
• Pentru 30% din punctaj N ≤ 106
• Pentru 60% din punctaj N ≤ 109 şi k ≤ 7

Exemplu:

kbin.in

15 3

kbin.out

45

Explicație

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
Numerele care au 3 biți de 1 sunt 7, 11, 13, 14.
s = 7 + 11 + 13 + 14 = 45.