Количество запросов
Даны два целых числа n, k. Рассмотрим функцию обработки запроса [from, to] деревом отрезков из вершины idx, которая соответствует отрезку массива [l, r] (from ≤ to, l ≤ r).
int get (int idx, int l, int r, int from, int to ) {
int ans = 1;
if (l == from r == to)
return ans ;
int mid = ( l + r ) / 2;
if (from <= mid)
ans += get ( 2 * idx + 1, l, mid, from, min (mid, to));
if (to >= mid + 1 )
ans += get ( 2 * idx + 2, mid + 1, r, max (from, mid + 1), to) ;
return ans ;
}
Нужно найти количество запросов [from, to] (0 ≤ from ≤ to ≤ n-1), таких что функция get(0, 0, n-1, from, to) вернет в качестве ответа k. Ответ выведите по модулю 10^9 + 9.
Входные данные
В первой строке записаны через пробел два целых числа: n (1 ≤ n ≤ 10^18), k (0 ≤ k ≤ 10^18).
Выходные данные
Выведите одно целое число — ответ на задачу 1000000009 (10^9 + 9).