Кількість запитів
Дано два цілих числа 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).