本題的記憶體限制為15MB
OwO學長,板橋高中資訊社的傳奇人物,在傳說中那一天降臨到了板橋高中。由於OwO學長的人氣極高,使得他馬上就被團團的粉絲包圍住,害得他陷入了即將被人群淹沒的危機,但OwO學長也是有備而來的,他馬上使出了不久前習得的分身術,並化作了無數個可見字元排成一列,變成了字串S。你知道OwO學長即使使用了分身術,也無法把本體強制換成其他型態,也就表示,OwO學長本尊依然還是會以OwO的型態存在著!不過OwO學長也早就料到這件事,不僅僅只有分身術,他更是使用了分裂術來混淆眾人的視線,當然,就算是分裂術,OwO三個字元的位置依然還是相對的。為了分析現況,請你撰寫一個程式,求出在OwO學長創造出的字串S中,OwO學長本尊的可能性有幾種。
首行有一個正整數T,代表有T筆測資。接下來T行,每行有一個字串S。
對於每行字串,輸出OwO學長的本尊可能性模109+7的餘數。
2 OwOwOb aObwcOd
4 1
本題共有四個子題,每一子題可有多筆測試資料:
第一子題的測試資料 T≦10,|S|≦100,全部解出可獲11分;
第二子題的測試資料 T≦10,|S|≦3000 ,全部解出可獲20分;
第三子題的測試資料 T≦10,|S|≦106,全部解出可獲31分;
第四子題的測試資料 T×|S|≦108,全部解出可獲38分;