2023 年上海市大学生程序设计竞赛 - 四月赛

B. CHAO!OP!

单点时限: 1.0 sec

内存限制: 1024 MB

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

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

摩斯电码对照表

请输出划分的方案数,对 $10^9+7$ 取模。

输入格式

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

输出格式

一行一个整数,表示答案,对 $10^9+7$ 取模。

样例

Input
0001011101
Output
370
Input
0111001100110111101101110
Output
5651126

提示

$0<\left|S\right|\le 10^6$