luogu#P11500. [ROIR 2019 Day 2] 间歇训练

[ROIR 2019 Day 2] 间歇训练

题目背景

翻译自 ROIR 2019 D2T2

题目描述

体育学院开发了一种新的间歇训练方法。根据这种方法,运动员每天都要训练,但负荷的增加和减少必须交替进行。

训练计划由一组正整数 a1,a2,,ama_{1}, a_{2}, \dots, a_{m} 组成,其中 aia_{i} 描述了运动员在第 ii 天的训练负荷。任何两个相邻的天数的负荷不能相同,即 aiai+1a_{i} \neq a_{i+1}。为了使负荷的增加和减少交替进行,aa 必须满足以下条件:如果 ai<ai+1a_{i}<a_{i+1},则 ai+1>ai+2a_{i+1}>a_{i+2};如果 ai>ai+1a_{i}>a_{i+1},则 ai+1<ai+2a_{i+1}<a_{i+2}

在整个训练计划中,总负荷必须为 nn,即 i=1mai=n\sum\limits_{i=1}^{m}a_i=n。计划的天数没有限制,即 mm 可以是任意值,但第一天的负荷是固定的,a1=ka_{1}=k

学院管理层想知道有多少不同的训练计划符合上述要求。你只需要求出其对 109+710^{9}+7 取模的结果。

输入格式

输入两个整数 nnkk,保证 1kn1\le k\le n

输出格式

输出符合要求的训练计划的数量对 109+710^9+7 取模的结果。

6 2
4
3 3
1

提示

样例解释

在样例 11 中,符合要求的计划有 [2,1,2,1],[2,1,3],[2,3,1],[2,4][2,1,2,1], [2,1,3], [2,3,1], [2,4]

在样例 22 中,唯一符合要求的计划为 [3][3]

数据范围

数据中 Subtask 0 为样例。

子任务 分值 1n1\le n\le
11 2323 1010
22 2020 3030
33 2323 500500
44 3434 50005000