83072 - 序列变换

给定两个长度为 n 的整数序列 B = [b_1, \ldots, b_n]，C = [c_1, \ldots, c_n]。对于长度为 n 的非负整数序列 D = [d_1, \ldots, d_n]，设 S(D) 为所有满足 $di = 0 的下标 i 的集合，定义 f(D) = \sum{i \in S(D)} bi，g(D) = \prod{i \in S(D)} c_i。特别地，若 S(D) 为空，则 f(D) = 0，g(D) = 1$。

小 L 有一个长度为 n 的 正整数序列 A = [a_1, \ldots, a_n]。小 L 可以对序列 A 做如下修改：

• 选择序列 A 的两个 相邻 的下标 i, j（即 1 \leq i, j \leq n 且 |i - j| = 1），若 a_i \leq a_j，则将 a_j 改为 a_j - a_i，同时将 a_i 改为 0。

小 L 可以进行任意多次修改操作，也可以不进行任何修改。对于所有序列 A 通过以上修改操作可以得到的序列 D，小 L 想求出 f(D) 的最大值以及 g(D) 之和，请你帮助他求出这两个值。形式化地，记 T(A) 为序列 A 通过以上修改操作可以得到的 所有序列的集合，你需要求出 $\max{D \in T(A)} f(D) 以及 \sum{D \in T(A)} g(D)。其中，由于 \sum_{D \in T(A)} g(D) 可能较大，你只需要求出其对 1,000,000,007$ 取模后的结果。

本题包含多组测试数据。

输入的第一行包含两个非负整数 c, t，分别表示测试点编号与测试数据组数。c = 0 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 n，表示序列长度。
• 第二行包含 n 个正整数 a_1, \ldots, a_n，表示序列 A。
• 第三行包含 n 个整数 b_1, \ldots, b_n，表示序列 B。
• 第四行包含 n 个正整数 c_1, \ldots, c_n，表示序列 C。

对于每组测试数据，仅输出一行，其中包含两个整数，分别表示 $\max{D \in T(A)} f(D) 以及 \sum{D \in T(A)} g(D) 对 1,000,000,007$ 取模后的结果。注意：\max_{D \in T(A)} f(D) 不需要对 1,000,000,007 取模。

本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见【评分方式】。

样例 1 解释

该样例共包含三组测试数据。

对于第一组测试数据，可以得到以下 4 个序列：

• D = [5, 6, 6]，f(D) = 0，g(D) = 1；
• D = [0, 1, 6]，f(D) = 3，g(D) = 1；
• D = [5, 0, 0]，f(D) = 6 + 9 = 15，g(D) = 2 \times 3 = 6；
• D = [0, 0, 5]，f(D) = 3 + 6 = 9，g(D) = 1 \times 2 = 2。

故 $\max{D \in T(A)} f(D) = \max{0, 3, 15, 9} = 15，\sum{D \in T(A)} g(D) = 1 + 1 + 6 + 2 = 10$。

设 N 为单个测试点内所有测试数据的 n 的和。对于所有测试数据，保证：

• 1 \leq t \leq 20；
• 1 \leq n \leq 5,000，N \leq 4 \times 10^4；
• 对于所有 1 \leq i \leq n，均有 1 \leq A_i \leq 10^9；
• 对于所有 1 \leq i \leq n，均有 -10^9 \leq B_i \leq 10^9；
• 对于所有 1 \leq i \leq n，均有 1 \leq C_i \leq 10^9。

NOI