Number of requests
Given two integers, n and k, consider the function that processes a query [from, to] using a segment tree starting from the node idx, which corresponds to the segment of the array [l, r] (from ≤ to, l ≤ r).
"'plaintext 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; "'
Your task is to determine the number of queries [from, to] (0 ≤ from ≤ to ≤ n-1) for which the function get(0, 0, n-1, from, to) returns k as the result. Output the answer modulo 10^9 + 9.
Input
The first line contains two integers separated by a space: n (1 ≤ n ≤ 10^18) and k (0 ≤ k ≤ 10^18).
Output
Output a single integer — the answer to the problem modulo 1000000009 (10^9 + 9).