Question

Задача на python
Условия

Однажды утром мама 5-классника Евлампия убиралась на антресолях и нашла бумажку, с которой тот часто играл в детстве. Мама помнит, что игрушка представляла собой волшебную строку, являющуюся ПСП1 из скобок 4 видов: (), [], {} и /\. К сожалению, почерк маленького Лампи оставлял желать лучшего, поэтому символы / и \ выглядят на бумажке, как просто |.

Тем не менее, маме любопытно узнать, сколько различных волшебных строк могло быть у её сыночка. Помогите ей и выведите данное число по простому модулю 1791791791 (возможно, мама ошиблась, и эта не та бумажка; в таком случае выведите 0).

1 Правильной скобочной последовательностью, или ПСП называется строка, которая может быть получена за конечное число шагов по следующим правилам:

• Пустая строка ε - ПСП. • Если строка A - ПСП, то строки (A), [A], {A}, /A\ тоже ПСП. • Если строки A и B - ПСП, то и строка AB - ПСП.

Замечание

В 1 тесте каким бы из 4 способов мы не заменяли || на / и \, ПСП всё равно не получится, так как всё портит подстрока {(}).

Во 2 тесте корректные ПСП, которые могли быть у Миши - ///\\\, //\/\\, //\\/\, /\//\\, /\/\/\.

Формат входных данных

В первой строке даётся число n (1 ≤ n ≤ 106) — длина строки, написанной на бумажке. Во второй строке располагается сама строка, состоящая только из символов ()[]{}|.

Формат выходных данных

Выведите единственное число — количество возможных ПСП, соответствующих написанной на бумажке строчке, которые могли быть игрушкой маленького Евлампия, по модулю 1791791791.

Примеры

Входные данные:

6 {(})||

Выходные данные:

0

Входные данные:

6 ||||||

Выходные данные:

5

Входные данные:

6 ({})[]

Выходные данные:

1

Answer 1

Ответ:

All Cups:Технокубок 2022/2023

Объяснение:

Вы будете сняты с соревнования за нарушение правил 'Технокубок 2022/2023' , c уважением © All Cups — проект VK. v3.32.23 / You will be removed from the competition for violating the rules of 'Technocup 2022/2023' , best regards © All Cups — VK project. v3.32.23