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 ')'.

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$.

Print a line with the answer. Since this number may be very large you should output the answer modulo $10^9+7$.

Input

4
((((
()))

Output

2

Input

3
())
)()

Output

0

Input

12
((()))(()())
((()))(()())

Output

1

Input

38
((((((((((((((((((((((((((((((((((((((
))))))))))))))))))))))))))))))))))))))

Output

767263183