x

Time limit5sMemory limit1536 MB

Summary

Count the distinct strings S' that a balanced bracket string could become after flipping one segment and then hiding some characters as x.

Level: Medium7 of 10
Topics: String, Dynamic programming, Brute force
Solved: No attempts yet

Problem

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

A security gate is installed at the doorway of JOI Company to prevent leaks of confidential information. Everyone must pass through the gate when entering or exiting the company. Two or more people cannot pass through the gate at the same time.

Each time a person passes through the gate, the gate records whether that person entered or exited the company. IOI-kun, an employee of JOI Company, has the gate record for one day. The record is a string S. If the i-th character of S is (, the i-th person to pass through the gate entered the company. If it is ), that person exited the company. IOI-kun knows that no one was inside the company at the start or at the end of that day.

Some strings made only of ( and ) cannot be a record. For example, ())( and (() are not valid records. The first would make the number of people inside negative, and the second would leave someone inside at the end of the day.

When IOI-kun checked the record, he found that a computer virus had modified S. The modification happened in two steps.

Choose a contiguous segment of S and flip every character in it. Each ( becomes ) and each ) becomes (. Call the result S'. The segment may have length 0, in which case S = S'.
Change zero or more characters of S' into x. Call the result S''.

IOI-kun does not remember S, so he wants to recover it from S''. As a first step, he wants to count the strings that can be S'. Be careful: count the possible S', not the possible S.

Given S'', compute the number of strings that can be S', modulo 1 000 000 007.

Input

The first line contains an integer N, the length of S''.

The second line contains the string S'', which consists of (, ), and x.

Output

Print one line containing the number of strings that can be S', modulo 1 000 000 007. If no such string exists, print 0.

Constraints

$1 \le N \le 300$ .

Examples4

Example 1
Input
```
4
x))x
```
Expected output
```
3
```
Example 2
Input
```
10
xx(xx()x(x
```
Expected output
```
45
```
Example 3
Input
```
5
x))x(
```
Expected output
```
0
```
Example 4
Input
```
10
xxxxxxxxxx
```
Expected output
```
684
```