Correct parentheses sequences can be defined recursively as follows:
- The empty string "" is a correct sequence.
- If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
- If "X" is a correct sequence, then "(X)" is a correct sequence.
- Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".
You are given two Strings s1 and s2.
Each character in these strings is a parenthesis, but the strings themselves are not necessarily correct sequences of parentheses.
You would like to interleave the two sequences so that they will form a correct parentheses sequence.
Note that sometimes two different ways of interleaving the two sequences will produce the same final sequence of characters.
Even if that happens, we count each of the ways separately.
(See Example 0 for a clarification.)
Compute and return the number of different ways to produce a correct parentheses sequence, modulo 10^9 + 7.