5068. CHAO!OP!

单点时限: 1.0 sec

内存限制: 1024 MB

古希腊哲学家哲学家沃·茨基·朔德说过:“命中间为什么有一横,是为了把人和 OP 分开。”

众所周知,济云星这个星球上的语言是摩斯电码,对应 26 个字母。最近济云星上出土了一本古代的书籍,可是因为年代久远,书籍上某篇文章的电码之间的间隔已经模糊不清。已知书是人写的,也是给人看的,那么它就不应该出现 OP 。现在将这篇文章的摩斯电码给你,请你算一算,这段电码有多少种划分方案,使得最后的文章不存在子串 OP

摩斯电码对照表

请输出划分的方案数,对 109+7 取模。

输入格式

一行一个字符串S,只包含 01 两个字符,其中 0 代表·1 代表-

输出格式

一行一个整数,表示答案,对 109+7 取模。

样例

Input
0001011101
Output
370
Input
0111001100110111101101110
Output
5651126

提示

0<|S|106

125 人解决,143 人已尝试。

137 份提交通过,共有 393 份提交。

2.8 EMB 奖励。

创建: 1 年,12 月前.

修改: 1 年,12 月前.

最后提交: 2 周,5 天前.

来源: N/A

题目标签
DP