Дана строка из букв «a» и «b». Мы хотим произвести над ней некоторые операции. На каждом шагу мы выбираем одну из подстрок «ab» в данной строке и заменяем ее на строку «bba». Если в строке нет подстрок «ab», то мы останавливаемся. Выведите минимальное число шагов, которое требуется нам сделать перед тем, как мы остановимся, по модулю 109 + 7.
Строка «ab» встречается как подстрока, если где-то есть буква «b» сразу после буквы «a».
Выходные данные
Выведите минимальное число шагов по модулю 109 + 7.
Примечание
Первый пример: «ab» → «bba».
Второй пример: «aab» → «abba» → «bbaba» → «bbbbaa».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ab
|
1
|
|
2
|
aab
|
3
|