题目描述

小蓝是一名星际探险家。在一次遗迹探索中，他发现了一块“星光石板”。

石板上从左到右一共有 $N$ 个凹槽。对于每个凹槽，小蓝都可以选择嵌入一颗“星之碎片”，记作 $1$；也可以保持空置，记作 $0$。这样一来，整块石板的状态就可以用一个长度为 $N$ 的 $01$ 串来表示。

根据遗迹的记载，石板会对“连续且完整的碎片段”产生共鸣。具体地，对于任意一个连续子区间 $[l, r]$（$1 \leq l \leq r \leq N$），如果这一段对应的凹槽全部都嵌入了碎片，也就是区间内每一位都是 $1$，那么这个区间就会产生一次“星光共鸣”。反之，只要其中出现过一个 $0$，这段区间就不会产生共鸣。

因此，一种填充方案所产生的“星光共鸣总次数”，就等于它的 $01$ 串中“全为 $1$ 的连续子区间”的数量。

例如，当 $N = 4$，石板状态为 $1101$ 时：

• $[1,1]$、$[2,2]$、$[4,4]$ 对应 $1$，各产生 $1$ 次共鸣；
• $[1,2]$ 对应 $11$，再产生 $1$ 次共鸣；
• 其他子区间如 $[2,3]$ 对应 $10$、$[3,4]$ 对应 $01$，这样的区间包含 $0$，不会产生共鸣。

所以该状态一共产生了 $4$ 次共鸣。

现在，小蓝打算枚举所有可能的填充方案。由于每个凹槽只有放与不放两种选择，总共有 $2^N$ 种不同的 $01$ 串。小蓝想知道：在这些方案中，有多少种方案的共鸣总次数至少为 $K$？

由于答案可能很大，请输出满足条件的方案数对 $10^9 + 7$ 取模后的结果。

输入格式

输入仅一行，包含两个整数 $N$ 和 $K$，表示石板上的凹槽数量，以及要求达到的最少“星光共鸣”次数。

输出格式

输出一个整数，表示满足“星光共鸣总次数不少于 $K$”的状态数量。由于答案可能很大，请输出对 $10^9 + 7$ 取模后的结果。

4 4

5

提示

【样例说明】

当 $N = 4$、$K = 4$ 时，共有 $5$ 种状态满足条件，分别为：

• $1110$: 共鸣次数为 $3 + 2 + 1 = 6 \geq 4$；
• $1101$: 共鸣次数为 $(2 + 1) + 1 = 4 \geq 4$；
• $1011$: 共鸣次数为 $1 + (2 + 1) = 4 \geq 4$；
• $0111$: 共鸣次数为 $6 \geq 4$；
• $1111$: 共鸣次数为 $4 + 3 + 2 + 1 = 10 \geq 4$。

所以答案为 $5$。

【评测用例规模与约定】

对于 $30\%$ 的数据，保证 $N \leq 12$；

对于 $100\%$ 的数据，保证 $1 \leq N \leq 1000$，$0 \leq K \leq \min(\frac{N(N+1)}{2}, 100)$。