题目背景

本题目来自仓库 https://github.com/Disposrestfully/CCPC-CQ-2024/tree/main

题目描述

给定一个长为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，你需要对 $a$ 进行若干次如下操作，使得 $a$ 中所有数均相等：

• 选择一段长为大于 $1$ 的奇数的区间 $a_l,a_{l+1},\ldots,a_r$，并将此区间内的所有数均替换为它们的中位数。

设最终 $a_1=a_2=\ldots=a_n=x$，我们定义序列 $a$ 的值为 $x$ 的最大值。

请你求出所有满足 $\forall\ 1\le i\le n$，$l_i\le a_i\le r_i$ 的整数序列 $a$ 的值之和。

由于答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数 $l_1,l_2,\ldots,l_n$。
• 第三行 $n$ 个整数 $r_1,r_2,\ldots,r_n$。

保证$1\le T\le 10$，$3\le n\le 150$，$1\le l_i\le r_i\le 10^9$。

输出格式

对于每组测试数据，输出一行一个整数表示答案对 $10^9+7$ 取模的结果。

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

1
5

提示

对于第一组测试数据，$a$ 只能为 $[1,1,1]$，值为 $1$，故答案为 $1$。

对于第二组测试数据，$a$ 可以为 $[1,1,1],[1,1,2],[1,2,1],[1,2,2]$，值分别为 $1,1,1,2$，故答案为 $5$。