FIICode 2025 Qualifying Round - Studenți | More or Less

Task

The relative order string $s$ of a permutation $[p_1,p_2,\ldots,p_n]$ is a string of $n-1$ characters from the set $\{\texttt{'<'},\texttt{'>'}\}$ which is constructed in the following way:

For every $1 \le i < n$:

• If $p_i < p_{i+1}$, then $s_i=\texttt{'<'}$.
• Otherwise, $s_i=\texttt{'>'}$.

You are given an integer $n$ and two strings $l$ and $r$ consisting of $n-1$ characters from the set $\{\texttt{'<'},\texttt{'>'}\}$.

Find the number of permutations $p$ of length $n$ which satisfy both of the following conditions:

• The relative order string of $p$ is lexicographically greater than or equal to $l$.
• The relative order string of $p$ is lexicographically less than or equal to $r$.

Since the answer can be very large, print its remainder modulo $10^9+7$.

Note: < is considered to be lexicographically smaller than >.

Input data

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 1\,000$) - the number of test cases. The next lines contain the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 4\,000$) - the length of array $a$.

The second line of each test case contains a string $l$ consisting of $n-1$ characters from the set $\{\texttt{'<'},\texttt{'>'}\}$.

The third line of each test case contains a string $r$ consisting of $n-1$ characters from the set $\{\texttt{'<'},\texttt{'>'}\}$.

It is guaranteed that, for all test cases, $r$ is lexicographically greater than or equal to $l$. Additionally, it is guaranteed that the sum of $n$ across all test cases does not exceed $10^4$.

Output data

For each test case, print the number of permutations of length $n$ whose relative order strings are lexicographically greater than or equal to $l$ and less than or equal to $r$.

Since this number can be very large, print its remainder modulo $10^9+7$.

Example

stdin

6
2
<
>
3
<>
<>
4
<<<
>><
4
<>>
><>
5
<><>
><><
15
<<<<<<>><<<<<>
<>><><><<><<<>

stdout

2
2
23
11
62
740226177

Explanation

In the first test case, both permutations of length $2$ have a relative order string which is lexicographically between < and >.

In the second test case, there are $2$ permutations whose relative order string is equal to <>: $[1,3,2]$ and $[2,3,1]$.

In the third and fourth test cases, there are $8$ possible relative order strings:

• <<<, which is the relative order string of $1$ permutation: $[1,2,3,4]$.
• <<>, which is the relative order string of $3$ permutations: $[1,2,4,3]$, $[1,3,4,2]$ and $[2,3,4,1]$.
• <><, which is the relative order string of $5$ permutations: $[1,3,2,4]$,
  $[1,4,2,3]$, $[2,3,1,4]$, $[2,4,1,3]$ and $[3,4,1,2]$.
• <>>, which is the relative order string of $3$ permutations: $[1,4,3,2]$,
  $[2,4,3,1]$ and $[3,4,2,1]$.
• ><<, which is the relative order string of $3$ permutations: $[2,1,3,4]$,
  $[3,1,2,4]$ and $[4,1,2,3]$.
• ><>, which is the relative order string of $5$ permutations: $[2,1,4,3]$, $[3,1,4,2]$, $[3,2,4,1]$, $[4,1,3,2]$ and $[4,2,3,1]$.
• >><, which is the relative order string of $3$ permutations: $[3,2,1,4]$, $[4,2,1,3]$ and $[4,3,1,2]$.
• >>>, which is the relative order string of $1$ permutation: $[4,3,2,1]$.

The number of permutations whose relative order strings are between <<< and >>< is equal to: $1+3+5+3+3+5+3=23$.

The number of permutations whose relative order strings are between <>> and ><> is equal to: $3+3+5=11$.