AT_iroha2019_day2_e 連呼
题目描述
いろは酱喊出了一个只包含 `A` 和 `B` 的字符串。
该字符串由 $N$ 个 `A` 和 $M$ 个 `B` 组成,长度为 $N+M$,第一个字符是 `A`,最后一个字符是 `B`。
此外,该字符串还包含 `AAA` 作为(连续的)子串。
请问作为いろは酱喊出的字符串,可能有多少种不同的字符串?请输出可能的字符串数对 $10^9+7$ 取模的结果。
输入格式
输入为以下格式:
> $N\ M$
输出格式
请输出答案,输出一行。
说明/提示
## 限制
- 输入均为整数
- $1 \leq N, M \leq 10^5$
## 说明
[题解](https://img.atcoder.jp/iroha2019-day2/editorial-E.pdf)
## 样例解释 1
满足条件的字符串有 `AAAABBB`、`AAABABB`、`ABBAAAB`、`AAABBAB`、`ABAAABB` 共 $5$ 种。
## 样例解释 2
满足条件的字符串只有 `AAABBBBBBBBBBBB`。
## 样例解释 3
不存在满足条件的字符串。
## 样例解释 4
请输出对 $10^9+7$ 取模的结果。
由 ChatGPT 4.1 翻译