Как-то раз Петя прочитал задачу про скобочную последовательность. Он долго думал над ней, но так и не нашел решение. Сегодня с этой задачей предстоит столкнуться вам.
Дана строка s, представляющая собой правильную скобочную последовательность. Правильная скобочная последовательность — это последовательность открывающихся («(») и закрывающихся («)») скобок такая, что из нее можно получить корректное математическое выражение, вставляя между скобок числа и операторы. Например, последовательности «(())()» и «()» правильные скобочные, а последовательности «)()» и «(()» нет.
В правильной скобочной последовательности каждой скобке соответствует парная скобка (открывающейся скобке соответствует парная закрывающаяся и наоборот). Например, в скобочной последовательности, изображенной на рисунке, третьей скобке соответствует парная шестая, а пятой скобке соответствует четвертая.
Вам разрешается раскрасить некоторые скобки в скобочной последовательности, так чтобы выполнялись все три условия:
- Каждая скобка либо не раскрашена, либо раскрашена в красный цвет, либо раскрашена в синий цвет.
- Для любых двух парных скобок раскрашена ровно одна скобка из этой пары. Другими словами, для каждой скобки верно следующее: раскрашена либо она сама, либо соответствующая парная к ней.
- Никакие две соседние раскрашенные скобки не имеют один и тот же цвет.
Найдите количество различных раскрасок скобочной последовательности удовлетворяющих описанным выше условиям. Две раскраски считаются различными, если они отличаются цветом хотя бы одной скобки. Так как ответ может быть достаточно большим, выведите его по модулю 1000000007 (109 + 7).
Примечание
Рассмотрим первый тестовый пример. Скобочную последовательность из этого примера можно раскрасить, например, как показано на двух рисунках ниже.
Две раскраски, показанные ниже, являются некорректными.
