Problem Description

Xiao Lan is an interstellar explorer. During an ancient ruin exploration, he found a “starlight tablet”.

There are $N$ grooves on the tablet from left to right. For each groove, Xiao Lan can choose to embed a “star shard”, denoted as $1$, or leave it empty, denoted as $0$. In this way, the state of the whole tablet can be represented by a binary string of length $N$.

According to the records in the ruin, the tablet resonates with “continuous and complete shard segments”. Specifically, for any contiguous subinterval $[l, r]$ ($1 \leq l \leq r \leq N$), if all grooves in this segment are embedded with shards, that is, every bit in the interval is $1$, then this interval will produce one “starlight resonance”. Otherwise, as long as there is a $0$ in it, this interval will not resonate.

Therefore, the “total number of starlight resonances” produced by a filling plan equals the number of contiguous subintervals that are all $1$ in its binary string.

For example, when $N = 4$ and the tablet state is $1101$:

• $[1,1]$, $[2,2]$, and $[4,4]$ correspond to $1$, each producing $1$ resonance;
• $[1,2]$ corresponds to $11$, producing another $1$ resonance;
• Other subintervals such as $[2,3]$ corresponding to $10$, and $[3,4]$ corresponding to $01$, contain $0$, so they do not resonate.

So this state produces a total of $4$ resonances.

Now, Xiao Lan plans to enumerate all possible filling plans. Since each groove has only two choices (place or not place), there are $2^N$ different binary strings in total. Xiao Lan wants to know: among these plans, how many plans have a total resonance count of at least $K$?

Since the answer may be very large, output the result modulo $10^9 + 7$.

Input Format

The input consists of one line containing two integers $N$ and $K$, representing the number of grooves on the tablet and the required minimum number of “starlight resonances”.

Output Format

Output one integer, representing the number of states whose “total number of starlight resonances is at least $K$”. Since the answer may be very large, output it modulo $10^9 + 7$.

4 4

5

Hint

Sample Explanation

When $N = 4$ and $K = 4$, there are $5$ states that meet the condition:

• $1110$: the resonance count is $3 + 2 + 1 = 6 \geq 4$;
• $1101$: the resonance count is $(2 + 1) + 1 = 4 \geq 4$;
• $1011$: the resonance count is $1 + (2 + 1) = 4 \geq 4$;
• $0111$: the resonance count is $6 \geq 4$;
• $1111$: the resonance count is $4 + 3 + 2 + 1 = 10 \geq 4$.

So the answer is $5$.

Constraints

For $30\%$ of the testdata, it is guaranteed that $N \leq 12$.

For $100\%$ of the testdata, it is guaranteed that $1 \leq N \leq 1000$, $0 \leq K \leq \min(\frac{N(N+1)}{2}, 100)$.

Translated by ChatGPT 5