Вам задана строка \(s\), состоящая из строчных букв «a», «b» и «c», а также из знаков вопроса «?».
Пусть количество знаков вопроса в строке \(s\) равно \(k\). Заменим каждый знак вопроса на одну из букв «a», «b» и «c». Таким образом, мы получим \(3^{k}\) всевозможных строк, состоящих только из букв «a», «b» и «c». Например, если \(s = \)«ac?b?c» после замены знаков вопроса мы получим строки \([\)«acabac», «acabbc», «acabcc», «acbbac», «acbbbc», «acbbcc», «accbac», «accbbc», «accbcc»\(]\).
Перед вами стоит задача определить количество подпоследовательностей «abc» во всех получившихся строках. Так как ответ может быть достаточно большим, выведите его по модулю числа \(10^{9} + 7\).
Подпоследовательность строки \(t\) — это такая последовательность, которую можно получить из строки \(t\) путем удаления некоторого (возможно нулевого) количества букв, при этом порядок оставшихся букв должен быть неизменным. Например, в строке «baacbc» есть две подпоследовательности «abc». Это подпоследовательность, состоящая из букв в позициях \((2, 5, 6)\), и подпоследовательность, состоящая из букв в позициях \((3, 5, 6)\).
Выходные данные
Выведите суммарное количество подпоследовательностей вида «abc» во всех строках, которые можно получить путем замены знаков вопроса на буквы «a», «b» и «c», по модулю \(10^{9} + 7\).
Примечание
В первом примере после замены знаков вопроса получим \(9\) строк:
- «acabac» — в этой строке \(2\) подпоследовательности «abc»,
- «acabbc» — в этой строке \(4\) подпоследовательности «abc»,
- «acabcc» — в этой строке \(4\) подпоследовательности «abc»,
- «acbbac» — в этой строке \(2\) подпоследовательности «abc»,
- «acbbbc» — в этой строке \(3\) подпоследовательности «abc»,
- «acbbcc» — в этой строке \(4\) подпоследовательности «abc»,
- «accbac» — в этой строке \(1\) подпоследовательность «abc»,
- «accbbc» — в этой строке \(2\) подпоследовательности «abc»,
- «accbcc» — в этой строке \(2\) подпоследовательности «abc».
Таким образом, во всех строках содержатся \(2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24\) подпоследовательности «abc».