2285: hehe
题目描述
As we all know, Fat Brother likes MeiZi every much, he always find some topic to talk with her. But as Fat Brother is so low profile that no one knows he is a rich-two-generation expect the author, MeiZi always rejects him by typing “hehe” (wqnmlgb). You have to believe that there is still some idealized person just like Fat Brother. They think that the meaning of “hehe” is just “hehe”, such like “hihi”, “haha” and so on. But indeed sometimes “hehe” may really means “hehe”. Now you are given a sentence, every “hehe” in this sentence can replace by “wqnmlgb” or just “hehe”, please calculate that how many different meaning of this sentence may be. Note that “wqnmlgb” means “我去年买了个表” in Chinese.
输入
输出
For each test case, output the case number first, and then output the number of the different meaning of this sentence may be. Since this number may be quite large, you should output the answer modulo 10007.
样例输入 复制
4
wanshangniyoukongme
womenyiqichuqukanxingxingba
bulehehewohaiyoushi
eheheheh
样例输出 复制
Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 3