Given an integer sequence $a_1, a_2, \dots, a_n$ of length $n$, you need to perform several operations on $a$ such that all numbers in $a$ become equal: * Choose a subsegment $a_l, a_{l+1}, \dots, a_r$ of odd length greater than 1, and replace all numbers in this subsegment with their median.

Let the final sequence be $a_1 = a_2 = \dots = a_n = x$. We define the value of the sequence $a$ as the maximum possible value of $x$. Calculate the sum of the values of all integer sequences $a$ that satisfy $\forall 1 \le i \le n, l_i \le a_i \le r_i$. Since the answer can be very large, please output the result modulo $10^9 + 7$.

Input

Read from standard input. The first line contains an integer $T$, representing the number of test cases. For each test case: The first line contains an integer $n$. The second line contains $n$ integers $l_1, l_2, \dots, l_n$. * The third line contains $n$ integers $r_1, r_2, \dots, r_n$.

It is guaranteed that $1 \le T \le 10$, $3 \le n \le 150$, $1 \le l_i \le r_i \le 10^9$.

Output

Output to standard output. For each test case, output a single integer on a new line representing the sum of the values modulo $10^9 + 7$.

Examples

Input 1

2
3
1 1 1
1 1 1
3
1 1 1
1 2 2

Output 1

1
5

Note 1

For the first test case, $a$ can only be $[1, 1, 1]$, the value is $1$, so the answer is $1$. For the second test case, $a$ can be $[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2]$, and their values are $1, 1, 1, 2$ respectively, so the answer is $5$.