Number of requests

Given two integers, $n$ and $k$, consider the function that processes a query [\mathrm{from},\ \mathrm{to}] using a segment tree starting from the node $\mathrm{idx}$, which corresponds to the segment of the array [l,\ r] (\mathrm{from} \leq \mathrm{to}, l \leq 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;
}

Your task is to determine the number of queries [\mathrm{from},\ \mathrm{to}] (0 \leq \mathrm{from} \leq \mathrm{to} \leq n-1) for which the function \mathrm{get}(0, 0, n-1, \mathrm{from}, \mathrm{to}) returns $k$ as the result. Output the answer modulo 10^9 + 9.