分数: 1300 点
问题陈述
有一个字符串 s 组成 a 和 b。
Snuke 可以以任意顺序执行任意次数的以下两种操作:
- 选择出现的
aa作为子字符串,并将其替换为b. - 选择出现的
bb作为子字符串,并将其替换为a.
有多少字符串 s 通过这一系列操作可以得到吗? 求计数模数 10^9 + 7.
约束
- 1 \leq |s| \leq 10^5
- s 包括
a和b.
输入
输入由标准输入按以下格式给出:
s
输出
打印字符串的数量 s 可以得到,模 10^9 + 7.
示例输入 1
aaaa
示例输出 1
6
可以获得六个字符串:
aaaaaabababaabba
示例输入 2
aabb
示例输出 2
5
可以获得五个字符串:
aabbaaabbbabba
示例输入 3
ababababa
示例输出 3
1
Snuke 无法执行任何操作。
示例输入 4
babbabaaba
示例输出 4
35