Jay的小迷弟
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

窗外的麻雀,在电线杆上多嘴。你说这一句,很有夏天的感觉。

作为Jay的小迷弟,LakerV非常想去Jay的演唱会。

有一天,他意外地发现他买的《周杰伦的床边故事》上出现了一行神秘的字符串,并且这本书给了他一个神奇的魔法。

现在,只要他能得到最多的”Jay”的碎片数量,他就能获得Jay演唱会的门票了。但兴奋的他现在正在打包行李,无暇考虑如何得到最多的”Jay”的碎片数量,请聪明的你告诉他该怎么做。

“Jay”碎片拼凑的规则:

如果原字符串中有’J’,’a’,’y’这三个字符,那么LakerV可以用它们得到一个“Jay”的碎片。

魔法使用方法:

如果原字符串中的有一个未被使用过的且连续的“Jay”字符串,那么LakerV可以用它们对当前手上“Jay”的碎片数量*2。

输入描述:

输入一行字符串(字符串长度不超过108)(字符串不包含空格)(保证所有字符均为小写或大写字母)

输出描述:

输出一行整数,表示LakerV能获得的最多的“Jay”碎片的数量
示例1

输入

复制
JayyaJ

输出

复制
2

说明

字符串总共有2个'J',2个'a',2个‘y'字符。最终LakerV手上有2个Jay碎片
示例2

输入

复制
JayJayyaJ

输出

复制
4

说明

最后三个字符yaJ有'y','a',J'三个字符,可以组成一个Jay碎片。现在LakerV手上有一个Jay碎片。前面有两个连续的Jay字符串,所以LakerV可以两次对手上的Jay碎片数量*2。最终LakerV手上有1*2*2=4个Jay碎片。
示例3

输入

复制
JayJ

输出

复制
1

说明

前面有三个字符'J','a','y'可以组成一个Jay碎片。最终LakerV手上有1个Jay碎片

备注:

1.魔法可以使用无限次

2.由于数可能非常大,所以需要对结果取模1e9+7

3.一开始LakerV手上”Jay”碎片的数量为0
4.未被使用过的且连续的“Jay”字符串如果用于魔法,那么该连续的“Jay”字符将不能用于得到一个“Jay”的碎片。