|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
Given two sequences of brackets $a$ and $b$ of length $n$, such that $a$ is not greater than $b$, you must count the number of balanced bracket sequences of length $n$ not less than $a$ and not greater than $b$. We assume comparisons are made in a lexicographical sense.
We define balanced bracket sequences as follows:
- The empty sequence is a balanced bracket sequence.
- If $s$ is a balanced bracket sequence, then so is $(s)$.
- If $s$ and $t$ are balanced bracket sequences, then so is $st$.
Given two sequences of brackets $x$, $y$ of length $n$, we say $x$ is lexicographically smaller than $y$ if they share a prefix of size $t \in [0, n-1]$ and $x[t+1] < y[t+1]$. You may assume character '(' is smaller than character ')'.
Input
The first line of input contains the integer $n$ $(1 \leq n \leq 10^3)$, the size of the sequences. Next two lines contain respectively sequences $a$ and $b$, composed only by characters '(' and ')'. It is guaranteed that sequence $b$ is not lexicographically smaller than $a$.
Output
Print a line with the answer. Since this number may be very large you should output the answer modulo $10^9+7$.
Sample test(s)
Input
4
((((
()))
Output
2
Input
3
())
)()
Output
0
Input
12
((()))(()())
((()))(()())
Output
1
Input
38
((((((((((((((((((((((((((((((((((((((
))))))))))))))))))))))))))))))))))))))
Output
767263183