D - Bracket sequence

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

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