【ZYCode R2】越狱

【ZYCode R2】越狱

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

YZB因为太菜被捕入监狱。这座监狱守备森严,YZB想要知道,这些罪犯能否越狱。

题目描述

监狱中有排成一行的 \(n\) 个牢房,关押着 \(n\) 名罪犯。这些罪犯组成了 \(m\) 个团体,当连续的多个牢房(至少2个)中,属于同一团体的罪犯达到了一半以上,他们就会越狱。

给定 \(n\),\(m\), 求有多少种情况下罪犯能越狱成功。我们认为两种情况不同当且仅当其中至少一个牢房内的罪犯属于的团体不同。

输入格式

一行两个整数 \(n\),\(m\)。

输出格式

一行一个整数表示总情况数。答案对 \(10^9+7\) 取模。

样例

样例输入 1

3 3

样例输出 1

6

样例输入 2

8 5

样例输出 2

14580

样例输入 3

998244353 114514

样例输出 3

223109856

提示说明

数据范围

对于 \(30\%\) 的数据

\( 3\le n\le10 \)

\( 3 \le m \le 5\)

对于 \(100\%\) 的数据

\(3\le m \le n\le10^{18}\)

数据保证 \(m \le n\)

ZYCode Normal Round #2

未参加
状态
已结束
规则
ACM/ICPC
题目
5
开始于
2023-05-12 20:45
结束于
2023-05-12 20:51
持续时间
0.1 小时
主持人
参赛人数
3