P16266 [Lanqiao Cup 2026 NOI Qualifier Python B Group] Starlight Resonance

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$.

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 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$.

### 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