Димитрий отлично знает, как находить сумму членов арифметической прогрессии, поэтому на этот раз ему дали задачку сложнее. Необходимо найти сумму $$$a_0 + a_1 + a_2 + ... + a_n$$$, где $$$a_i$$$ отличается от $$$i$$$ только $$$k$$$-ым битом справа в своей двоичной записи. Если число содержит недостаточно двоичных цифр, следует добавить незначащие нули слева.
Два целых числа $$$n$$$ и $$$k$$$, где $$$0 \le n \le 10^9$$$ и $$$1 \le k \le 30$$$.
Одно целое число — ответ на задачу.
7 3
28
5 3
23
При $$$k = 3$$$ последовательность $$$\{a_n\}$$$ будет выглядеть следующим образом: 4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, ...
