CF2027D2.The Endspeaker (Hard Version)

这是这道题目的困难版本。与简单版本的区别在于，你还需要输出达到最优解的操作序列数量。你需要解决这两种版本才能进行 hack。

现在给定一个数组 $ a $，长度为 $ n $，以及一个数组 $ b $，长度为 $ m $（保证 $ b_i > b_{i+1} $ 对所有 $ 1 \le i < m $ 成立）。初始时，$ k $ 的值为 $ 1 $。你的目标是通过执行以下两种操作之一反复将数组 $ a $ 变为空：

• 类型 $ 1 $ 操作 — 在 $ k < m $ 且数组 $ a $ 不为空时，你可以将 $ k $ 的值加 $ 1 $。这种操作不需要花费任何代价。
• 类型 $ 2 $ 操作 — 你可以移除数组 $ a $ 的一个非空前缀，使得这个前缀的和不大于 $ b_k $。这种操作的代价为 $ m - k $。

你需要让将数组 $ a $ 变为空的总操作代价最小化。如果无法通过任何操作序列达到这一目标，请输出 $ -1 $。否则，输出最小总操作代价以及产生命中该代价的操作序列数量，对 $ 10^9 + 7 $ 取模。

若两个操作序列在任一步骤中选择了不同种类的操作，或移除前缀的大小不同，则它们视为不同。

每个测试用例包含多个测试，第一行为测试用例数量 $ t $（$ 1 \le t \le 1000 $）。接下来描述每个测试用例。

每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n, m \le 3 \cdot 10^5 $，且 $ 1 \le n \cdot m \le 3 \cdot 10^5 $）。

每个测试用例的第二行包含长度为 $ n $ 的整数数组 $ a $，其中每个 $ a_i $ 满足 $ 1 \le a_i \le 10^9 $。

每个测试用例的第三行包含长度为 $ m $ 的整数数组 $ b $，$ 1 \le b_i \le 10^9 $，并且满足 $ b_i > b_{i+1} $ 对所有 $ 1 \le i < m $。

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

对于每个测试用例，如果可以使数组 $ a $ 变为空，则输出两个整数：最小的操作总费用，以及达到该最小费用的操作序列数量，结果对 $ 10^9 + 7 $ 取模。

如果没有可能的操作序列能使数组 $ a $ 变为空，则输出单个整数 $ -1 $。

以下为一个测试用例的示例，其中最优操作序列的总费用为 $ 1 $，共有 $ 3 $ 种：

• 所有这 $ 3 $ 种序列都以类型 $ 2 $ 的操作开头，移除前缀 $ [9] $，使得 $ a = [3, 4, 3] $，产生代价 $ 1 $。然后执行类型 $ 1 $ 操作，把 $ k $ 提升一位，此后所有操作均无代价。
• 一种序列依次移除前缀 $ [3, 4] $ 和 $ [3] $。
• 另一种序列依次移除前缀 $ [3] $ 和 $ [4, 3] $。
• 还有一种序列依次移除前缀 $ [3] $，再移除 $ [4] $，最后移除 $ [3] $。

在第二个测试用例中，由于 $ a_1 > b_1 $，无法移除任何前缀，因此无论如何都无法使数组 $ a $ 变为空。

本翻译由 AI 自动生成