17688번 - Security Gate 서브태스크다국어

Do you know Just Odd Inventions Co., Ltd.? The business of this company is doing “just odd inventions.” Here we just call it JOI Company.

There is a security gate installed in the doorway of JOI Company, in order to prevent confidential information leaks. One must pass through the gate when entering or exiting the company. It is impossible for two or more people to pass through the gate at the same time.

Whenever a person pass through this gate, it records the information indicating that a person enters or exits the company. Now, IOI-kun, an employee of JOI Company, has a record of the gate for some day. The record is represented by string S : if the i-th character of S is ‘(’, it means that the i-th person who passed through the gate entered the company, and if the i-th character of S is ‘)’, it means that the i-th person who passed through the gate exited the company. IOI-kun knows that there were no people inside JOI Company at the beginning or at the end of this day. Note that there exist strings consisting only of ‘(’ and ‘)’ which cannot represent a record: for example, a record cannot be ())( or (() because it would follow that the number of people inside JOI Company had become negative or there had been a person inside JOI Company at the end of the day, respectively.

The next moment IOI-kun checked the record, the string S was modified by a computer virus spread across JOI Company! After some investigation, he supposed that the modification took the following process:

• First, a contiguous segment in S changed as follows: for each character in the segment, if it was ‘(’ then it became ‘)’, and if it was ‘)’ then it became ‘(’. We denote the string after this change by S′. The length of the changed segment might be 0, that is, S = S′.
• Then, 0 or more characters in S′ became ‘x’. We denote the string after this change by S′′.

IOI-kun does not remember S , so he tries to recover S from S′′. For that, he wants first to count the number of strings which can be S′ (not S , be careful).

Given string S′′, write a program which calculates the number of strings which can be S′, modulo 1 000 000 007.

Read the following data from the standard input.

• The first line of the input contains an integer N. This means that length of S′′, the string after the modification, is N.
• The second line of the input contains a string S′′, each character of which is ‘(’, ‘)’ or ‘x’. This means that the string after the modification is S′′.

Write one line to the standard output. The output should contain the number of strings which can be S′, modulo 1 000 000 007. If there is no such string, output 0.

• 1 ≤ N ≤ 300.

• N ≤ 100.
• The number of ‘x’s in S′′ is at most 4.

• N ≤ 100.
• The number of ‘x’s in S′′ is at most 12.

• N ≤ 100.
• The number of ‘x’s in S′′ is at most 20.

• N ≤ 100.

There are no additional constraints.