Крепление парусов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Моана отправляется с Мауи в новое путешествие. Но и в этот раз ее настигает сильный шторм — чтобы лодку не потопило, ей необходимо правильно закрепить паруса.

Паруса закреплены $$$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$$$.