C. Номер строки

Выпишем все строки длины $N$ из нулей и единиц, содержащие ровно $K$ единиц, в лексикографическом порядке и пронумеруем их с единицы.

По данной строке найдите её номер.

Выписывать список нельзя: строк может быть больше $10^{17}$. Считать надо по-другому: пройти по строке слева направо и на каждой единице прибавить количество строк, которые начинались бы с нуля в этой позиции при том же префиксе.

Первая строка содержит числа $N$ и $K$ ($0 \le K \le N \le 60$).

Вторая строка содержит строку длины $N$ из нулей и единиц ровно с $K$ единицами.

Гарантируется, что $\binom{N}{K}$ помещается в 64-битный тип.

Одно число — номер строки.