Даны две целочисленные последовательности длины $n$: $B=[b_1,\ldots,b_n]$ и $C=[c_1,\ldots,c_n]$. Для последовательности неотрицательных целых чисел $D=[d_1,\ldots,d_n]$ длины $n$ обозначим через $S(D)$ множество всех индексов $i$, для которых $d_i=0$, и определим $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 есть последовательность положительных целых чисел $A=[a_1,\ldots,a_n]$ длины $n$. 小L может изменять её следующим образом:

• Выбрать два соседних индекса $i,j$ последовательности $A$ (то есть $1\le i,j\le n$ и $|i-j|=1$). Если $a_i\le a_j$, заменить $a_j$ на $a_j-a_i$, одновременно заменив $a_i$ на $0$.

小L может выполнить произвольное число операций, в том числе ни одной. Среди всех последовательностей $D$, которые можно получить из $A$ этими операциями, 小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$.

Входные данные

Данные считываются из файла sequence.in.

В задаче несколько наборов входных данных.

Первая строка содержит два неотрицательных целых числа $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$.

Выходные данные

Вывод производится в файл sequence.out.

Для каждого набора данных выведите одну строку с двумя целыми числами: $\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

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

Выходные данные 1

15 10
1 18
37 48

Примечание

Этот пример содержит три набора данных.

Для первого набора можно получить следующие четыре последовательности:

• $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\times3=6$;
• $D=[0,0,5]$, $f(D)=3+6=9$, $g(D)=1\times2=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$.

Пример 2

См. файлы sequence/sequence2.in и sequence/sequence2.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $3,4$.

Пример 3

См. файлы sequence/sequence3.in и sequence/sequence3.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $5,6$.

Пример 4

См. файлы sequence/sequence4.in и sequence/sequence4.ans в каталоге участника.

Этот пример удовлетворяет ограничениям теста $7$.

Пример 5

См. файлы sequence/sequence5.in и sequence/sequence5.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $11,12$.

Пример 6

См. файлы sequence/sequence6.in и sequence/sequence6.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $16\sim18$.

Ограничения

Пусть $N$ — сумма значений $n$ по всем наборам данных одного теста. Для всех наборов гарантируется:

• $1\le t\le20$;
• $1\le n\le5000$, $N\le4\times10^4$;
• для всех $1\le i\le n$ выполняется $1\le A_i\le10^9$;
• для всех $1\le i\le n$ выполняется $-10^9\le B_i\le10^9$;
• для всех $1\le i\le n$ выполняется $1\le C_i\le10^9$.

Особое свойство A: гарантируется $A_1=A_2=\cdots=A_n=1$.

Особое свойство B: гарантируется, что для всех $1\le i\le n$ значение $A_i$ независимо и равномерно случайно выбирается из $[1,10^9]$.

Подзадачи

Для каждого теста:

• Правильные ответы $\max_{D\in T(A)}f(D)$ для всех наборов данных дают $40\%$ баллов за тест.
• Правильные ответы $\sum_{D\in T(A)}g(D)$ по модулю $1{,}000{,}000{,}007$ для всех наборов данных дают $60\%$ баллов за тест.

Внимание: даже если вы отвечаете только на один из вопросов, всё равно необходимо вывести два целых числа в соответствии с форматом вывода, соответствующие ответам на оба вопроса.