A16548 | Sakura Adachi and Optimal Sequences

“真令人头疼……”

—— Hougetsu Shimamura

Adachi 正在为一道世代传承的难题抓耳挠腮……呃，对，就是这道题！反正，请你帮她解决吧！

你有两个长度为 $n$ 的数组 $a$ 和 $b$，满足 $1\leq a_i\leq b_i$。

每次操作，你可以：

- 选择一个下标 $i$（$1 \leq i \leq n$），令 $a_i := a_i + 1$，或者
- 使 $a$ 的所有元素都乘以 $2$。

记 $x$ 为将 $a$ 变为 $b$ 所需的最少操作次数。长度为 $n$ 的两个数组 $a$ 和 $b$，当且仅当对于所有 $1 \leq i \leq n$ 都有 $a_i = b_i$ 时，认为 $a = b$。

求 $x$ 的值。此外，计算用恰好 $x$ 次操作将 $a$ 变为 $b$ 的不同操作序列数量。若对于任意 $1 \leq j \leq x$，两条操作序列第 $j$ 步所选的操作类型或下标不同，则认为这两条操作序列不同。

由于方案数可能很大，请将答案对 $10^6+3$ 取模输出。注意 $10^6+3$ 是一个质数。

第一行包含一个整数 $t$（$1\leq t\leq 10^4$），表示测试用例数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i\leq 10^6$）。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$a_i \leq b_i \leq 10^6$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出两个整数 $x$，以及用恰好 $x$ 次操作将 $a$ 变为 $b$ 的不同操作序列数量，对 $10^6+3$ 取模。$x$ 的值应按通常方式输出，不需要取模。