Моана отправляется с Мауи в новое путешествие. Но и в этот раз ее настигает сильный шторм — чтобы лодку не потопило, ей необходимо правильно закрепить паруса.
Паруса закреплены $$$n$$$ узлами, каждый из которых может находиться в одном из трех состояний:
Сейчас все узлы находятся в состоянии 'w'. За одно действие Моана может выбрать отрезок поряд идущих номеров узлов и
Вам дана последовательность из $$$q$$$ действий, которые Моане надо выполнить, но для каждого действия известно только в какое состояние надо перевести какой-то отрезок узлов (то есть вся последовательность задается строкой из букв 'r' и 'b').
Определите количество возможных конфигураций узлов после выполнения всей последовательности действий. Две конфигурации называются различными, если найдется хотя бы один узел, который в них находится в различных состояниях. Поскольку ответ может быть слишком большой, выведите остаток от его деления на $$$10^9 + 7$$$.
В первой строке даны два целых числа $$$n$$$ и $$$q$$$ — количество узлов и количество действий ($$$1 \le n, q \le 70$$$).
Далее следует строка из $$$q$$$ символов, каждый из которых равен 'r' или 'b' и задает перевод очередного отрезка узлов в соответствующее состояние.
Выведите единственное число — количество различных конфигураций узлов после выполнения всей последовательности действий, по модулю $$$10^9 + 7$$$.
2 1 r
4
3 2 rb
22
6 4 rbrb
627
В первом примере из условия единственным действием можно выбрать любой из четырех отрезков: пустой, $$$[1]$$$, $$$[2]$$$, $$$[1, 2]$$$.
Во втором примере возможны следующие конфигурации парусов: все белые, любой отрезок красный ($$$6$$$ вариантов), любой отрезок синий (еще $$$6$$$ вариантов), один красный и один синий рядом ($$$4$$$ варианта), и еще $$$5$$$ вариантов на случай, если первым действием выбрать отрезок $$$[1, 2, 3]$$$, а вторым — произвольный синий длины $$$1$$$ или $$$2$$$.