SP12807 SPP2 - Recursive Sequence (Version X)

我们定义自然数序列 \(a_i\) 如下： - 当 \(i \leq m\) 时，\(a_i = b_i\) - 当 \(i > t\) 时，\(a_i = c_1 a_{i-1} + c_2 a_{i-2} + \ldots + c_t a_{i-t}\) 在这里，\(b_j\) 和 \(c_j\) 是已知的自然数。你的任务是计算 \(a_n\) 并将结果对 \(10^9 + 7\) 取模。 上述描述来源于原题 [SEQ](http://spoj.com/problems/SEQ)。为了增加题目的复杂性，我们将描述稍作修改：绝大多数 \(i > m\) 的情况下，\(a_i\) 依旧遵循上述公式，但有 \(q\) 个例外，即 \(n_1, n_2, \ldots, n_q\)： - 对于这些例外的 \(i\)（即 \(1 \leq i \leq q\)），我们有：\(a_{n_i} = d_{i1} a_{n_i-1} + d_{i2} a_{n_i-2} + \ldots + d_{it_i} a_{n_i-t_i}\)

每组测试数据的首行包含三个整数：\(n\)（满足 \(m < n \leq 10^9\））、\(m\)（满足 \(1 \leq m \leq 100\））和 \(q\)（满足 \(0 \leq q \leq 100\)）。第二行包括 \(m\) 个整数 \(b_1, b_2, \ldots, b_m\)。接下来的第三行首先包含一个整数 \(t\)，接着是 \(t\) 个整数：\(c_1, c_2, \ldots, c_t\)。随后的 \(q\) 行用于描述 \(q\) 种特殊情况，每行先给出 \(n_i\) 和 \(t_i\)，然后是 \(t_i\) 个整数：\(d_{i1}, d_{i2}, \ldots, d_{it_i}\)。所有 \(n_i\) 互不相同。所有的整数保证为非负，且除非另有说明，所有数不大于 \(10^9\)。输入以 EOF 为结束。可假设所提供的输入数据都是有效的，即所有需要的数都可以唯一确定。

对于每个测试用例，输出一行结果。请参考示例以获取更多的格式细节。

- \(m < n \leq 10^9\) - \(1 \leq m \leq 100\) - \(0 \leq q \leq 100\) **本翻译由 AI 自动生成**