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