春天来了,校园里春意盎然。小潍在校园里采摘了 $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$ 。
