Logo Wy Online Judge

WyOJ

时间限制:1 s 空间限制:512 MB 控制组: group_default 压缩包大小: 6.935 KB
统计

春天来了,校园里春意盎然。小潍在校园里采摘了 $n$ 朵鲜花,打算装饰在农场的 $m$ 个栅栏上,这样每个栅栏上就有 $a_1,a_2,...a_m$ 朵鲜花。小潍希望鲜花错落有致,他要求按照下面的规则打扮栅栏: - 第一个栅栏的鲜花朵数是固定的 $a_1=k$ 。

  • 相邻栅栏间的鲜花朵数满足条件 $a_{i-1}a_{i+1}$ 或者 $a_{i-1}a_{i+1}$ 。

  • $\sum _{i=1}^m a_i=n$ 。

  • $m $ 可以是任意值。 小潍想知道共有多少种可行的方案来安排这些鲜花?方案数可能很多,输出其对 $1e9+7 $ 取模的结果。

输入格式

输入两个整数 $n$ 和 $k$,保证 $1\leq k \leq n$。

输出格式

输出符合要求安排方案数量对 $1e9+7 $ 取模的结果。

样例输入1

8 3

样例输出1

5

样例解释1

共有 $(3, 5)$ 、$(3,4,1)$、$(3,2,3)$、$(3 ,1, 4)$、$(3, 1, 3 ,1)$ 这 $5$ 种装饰栅栏的方案。

样例输入2

400 6

样例输出2

872560393

样例输入3

见下发文件flower\flower3.in

样例输出3

见下发文件flower\flower3.ans

数据规模与约定

对于 $20\%$ 的数据,$1 \leq n \leq 10$ 。 对于 $40\%$ 的数据,$1 \leq n \leq 500$ 。 对于 $100\%$ 的数据,$1 \leq n \leq 5000 ,k \leq n$ 。