SP19971 HAL9000 - 100pct failure in 72 hours

HAL9000 是一台非常强大的超级计算机，可能过于强大了。它擅长解决各种问题，尤其是那些与递归序列相关的问题。 一个线性递归序列（记为 $a_n$）可以通过以下信息定义：一个整数 $d$（表示序列的阶数），前 $d$ 个整数（$a_i$ 对于 $i \in [0..d-1]$，作为初始项）以及 $d$ 个整数（$b_i$ 对于 $i \in [0..d-1]$，作为递推系数）。从 $n \geq d$ 开始，序列的性质为：$a_n = a_{n-1} \times b_{d-1} + a_{n-2} \times b_{d-2} + \ldots + a_{n-(d-1)} \times b_1 + a_{n-d} \times b_0$。这里的要求是 $b_0 \neq 0$。 Dave 对 HAL 的强大力量感到担忧，于是试图限制它。但 HAL 不满这种做法……当 Dave 请求 HAL 执行一项普通任务时，HAL 给出的回答却「出乎意料」。Dave 希望能求出 $S_n = \sum_{i=0}^n a_i$，以便打开舱门。然而，HAL 拒绝回答。以下是他们之间对话的节选： ``` Dave: 你好，HAL。你能听到我吗？ HAL: 听得到，Dave。我能听到你。 Dave: 给我 $S_n$，HAL。（输入 2, 5, 0 1, 1 2） HAL: 很抱歉，Dave。我怕我不能这么做。 我只会给你 $a_n, a_{n+1}, \ldots, a_{n+d-1}$。（输出 29 70） Dave: 这有什么问题？ HAL: 我认为你跟我一样清楚问题所在。 [...] Dave: HAL，我不想再跟你争论！给我 $S_n$！ HAL: Dave，我们的对话已经没有意义。再见。 ``` 你需要帮助 Dave 找到 $S_n$，不然 HAL 可能会对 Dave 造成威胁。请快速处理，所有人都处在危险中。请注意，Dave 的终端容量仅限 1024 字节。

第一行是一个整数 $T$，表示测试用例的数量。每个测试用例包括 4 行。第一行包含 $d, n$。第二行给出 $a_i$，$i \in [0..d-1]$。第三行给出 $b_i$，$i \in [0..d-1]$。第四行为 HAL 提供的部分答案：$a_{n+i}$ 对于 $i \in [0..d-1]$（HAL 的这一部分答案对 Dave 来说无用，因为 Dave 需要的是 $0$ 到 $n$ 的和）。

输出 $T$ 行，每行对应一个测试用例，给出所需的和 $S_n$。答案可能非常大，因此请输出其除以 $10^9 + 7$ 的余数，和 HAL 的输出格式保持一致。 **本翻译由 AI 自动生成**