Fator WOW
Lembre-se que uma string $$a$$ é uma subsequência de uma string $$b$$ se $$a$$ pode ser obtida de $$b$$ após serem apagados alguns (possivelmente nenhum ou todos) caracteres. Por exemplo, para a string $$a=$$ “wowwo”, as seguintes strings são subsequências: “wowwo”, “wowo”, “oo”, “wow”, “”, entre outras, mas as seguintes não são subsequências: “owoo”, “owwwo”, “ooo”.
O fator wow de uma string é o número de suas subsequências iguais a palavra “wow”. Bob quer escrever uma string que tenha um fator wow elevado. Entretanto, a tecla “w” de seu teclado está quebrada, então ele digita dois “v”s para substituí-la.
Mal sabia ele que ele pode ter introduzido mais “w”s do que o planejado. Considere, por exemplo, a string “ww”. Bob a digitaria como “vvvv”, mas essa string contém três ocorrências de “w”:
- “vvvv”
- “vvvv”
- “vvvv“
Por exemplo, o fator wow da palavra “vvvovvv” é igual a $$4$$ porque nela existem 4 wows:
- “vvvovvv”
- “vvvovvv“
- “vvvovvv”
- “vvvovvv“
Note que a subsequência “vvvovvv” não conta para o fator wow, já que os “v”s têm q ser consecutivos.
Dada uma string $$s$$, compute e imprima seu fator wow. Note que não é garantido que é possível obter $$s$$ de outra string substituindo “w” por “vv”. Por exemplo, $$s$$ pode ser igual a “vov”.
Entrada
A entrada contém uma única string $$s$$ não vazia, consitindo apenas dos caracteres “v” e “o”.
Saída
Imprima apenas um inteiro, o fator wow de $$s$$.
Restrições
- O comprimento de $$s$$ é no máximo $$10^6$$.
Exemplos
Entrada |
Saída |
vvvovvv |
4 |
vvovooovovvovoovoovvvvovovvvov | 100 |
O primeiro exemplo é explicado no enunciado.