Given two integer sequences $B = [b_1, \dots, b_n]$ and $C = [c_1, \dots, c_n]$ of length $n$. For a non-negative integer sequence $D = [d_1, \dots, d_n]$ of length $n$, let $S(D)$ be the set of all indices $i$ such that $d_i = 0$. Define $f(D) = \sum_{i \in S(D)} b_i$ and $g(D) = \prod_{i \in S(D)} c_i$. Specifically, if $S(D)$ is empty, then $f(D) = 0$ and $g(D) = 1$.

Little L has a positive integer sequence $A = [a_1, \dots, a_n]$ of length $n$. Little L can modify sequence $A$ as follows: * Choose two adjacent indices $i, j$ in sequence $A$ (i.e., $1 \le i, j \le n$ and $|i - j| = 1$). If $a_i \le a_j$, then change $a_j$ to $a_j - a_i$ and change $a_i$ to $0$.

Little L can perform this modification operation any number of times, or not at all. For all sequences $D$ that can be obtained from sequence $A$ through the above modification operations, Little L wants to find the maximum value of $f(D)$ and the sum of $g(D)$. Please help him find these two values. Formally, let $T(A)$ be the set of all sequences that can be obtained from sequence $A$ through the above modification operations. You need to calculate $\max_{D \in T(A)} f(D)$ and $\sum_{D \in T(A)} g(D)$. Since $\sum_{D \in T(A)} g(D)$ may be large, you only need to output the result modulo $1,000,000,007$.

Input

The input is read from the file sequence.in.

This problem contains multiple test cases. The first line contains two non-negative integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c = 0$ indicates that this test case is a sample.

The following lines contain the test data for each test case: The first line contains a positive integer $n$, representing the length of the sequence. The second line contains $n$ positive integers $a_1, \dots, a_n$, representing sequence $A$. The third line contains $n$ integers $b_1, \dots, b_n$, representing sequence $B$. The fourth line contains $n$ positive integers $c_1, \dots, c_n$, representing sequence $C$.

Output

The output is written to the file sequence.out.

For each test case, output a single line containing two integers, representing $\max_{D \in T(A)} f(D)$ and the result of $\sum_{D \in T(A)} g(D)$ modulo $1,000,000,007$, respectively. Note: $\max_{D \in T(A)} f(D)$ does not need to be taken modulo $1,000,000,007$.

This problem consists of two sub-questions. Correctly answering either one will earn partial points. Please refer to the Scoring section for details.

Constraints

Let $N$ be the sum of $n$ over all test cases in a single test point. For all test cases, it is guaranteed that: $1 \le t \le 20$; $1 \le n \le 5,000$, $N \le 4 \times 10^4$; For all $1 \le i \le n$, $1 \le A_i \le 10^9$; For all $1 \le i \le n$, $-10^9 \le B_i \le 10^9$; * For all $1 \le i \le n$, $1 \le C_i \le 10^9$.

Special Property A: Guaranteed $A_1 = A_2 = \dots = A_n = 1$. Special Property B: Guaranteed that for all $1 \le i \le n$, $A_i$ are generated independently and uniformly at random in $[1, 10^9]$.

Scoring

For each test point: Correctly answering $\max_{D \in T(A)} f(D)$ for all test cases earns 40% of the points for that test point. Correctly answering $\sum_{D \in T(A)} g(D)$ modulo $1,000,000,007$ for all test cases earns 60% of the points for that test point.

Note: Even if you only answer one of the questions, you must still output two integers in the specified format, corresponding to the answers for both questions.

Examples

Input 1

0 3
3
5 6 6
3 6 9
1 2 3
6
1 1 4 5 1 4
-1 1 -1 1 -2 2
1 1 1 1 1 1
8
4 2 4 2 2 2 4 4
-2 4 9 -3 4 8 7 8
1 1 1 1 1 1 1 1

Output 1

15 10
1 18
37 48

Note 1

This sample contains three test cases. For the first test case, the following 4 sequences can be obtained: $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$. Thus, $\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$.