题目描述

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

小 L 有一个长度为 $n$ 的正整数序列 $A = [a_1, \dots, a_n]$，可对序列 $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$。可进行任意多次修改操作或不操作。对于所有序列 $A$ 通过修改操作可得到的序列 $D$，需求出 $f(D)$ 的最大值以及 $g(D)$ 之和（$g(D)$ 之和对 $10^9 + 7$ 取模）。形式化地，记 $T(A)$ 为序列 $A$ 可得到的所有序列的集合，需求出 $\max_{D \in T(A)} f(D)$ 以及 $\sum_{D \in T(A)} g(D) \mod 10^9 + 7$。

输入格式

1. 第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数，$c = 0$ 表示该测试点为样例。
2. 每组测试数据：
   • 第一行包含一个正整数 $n$，表示序列长度。
   • 第二行包含 $n$ 个正整数 $a_1, \dots, a_n$，表示序列 $A$。
   • 第三行包含 $n$ 个整数 $b_1, \dots, b_n$，表示序列 $B$。
   • 第四行包含 $n$ 个正整数 $c_1, \dots, c_n$，表示序列 $C$。

输出格式

对于每组测试数据，输出一行两个整数，分别表示 $\max_{D \in T(A)} f(D)$ 以及 $\sum_{D \in T(A)} g(D) \mod 10^9 + 7$。即使仅回答其中一个问题，也需按格式输出两个整数。

样例1

输入

0 1
3
5 6 6
3 6 9
1 2 3

输出

15 10

样例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) = 15$，$\sum_{D \in T(A)} g(D) = 1 + 1 + 6 + 2 = 10$。

数据范围

设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。

• $1 \leq t \leq 20$。
• $1 \leq n \leq 5000$，$N \leq 4 \times 10^4$。
• 对于所有 $1 \leq i \leq n$，$1 \leq A_i \leq 10^9$，$-10^9 \leq B_i \leq 10^9$，$1 \leq C_i \leq 10^9$。

特殊性质说明：

• A：保证 $A_1 = A_2 = \cdots = A_n = 1$。
• B：保证对于所有 $1 \leq i \leq n$，$A_i$ 均在 $[1, 10^9]$ 中独立均匀随机生成。

评分方式

对于每个测试点：

• 正确回答所有测试数据的 $\max_{D \in T(A)} f(D)$，可获得该测试点 $40\%$ 的分数。
• 正确回答所有测试数据的 $\sum_{D \in T(A)} g(D) \mod 10^9 + 7$，可获得该测试点 $60\%$ 的分数。