給定兩個長度為 $n$ 的整數序列 $B=[b_1,\ldots,b_n]$、$C=[c_1,\ldots,c_n]$。對於長度為 $n$ 的非負整數序列 $D=[d_1,\ldots,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,\ldots,a_n]$。小 L 可以對序列 $A$ 做如下修改：
- 選擇序列 $A$ 的兩個相鄰的下標 $i,j$（即 $1\le i,j\le n$ 且 $|i-j|=1$），若 $a_i\le 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$ 取模後的結果。
輸入格式
從檔案 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
說明
該範例共包含三組測試資料。
對於第一組測試資料，可以得到以下 $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\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$。
| 測試點編號 | $n\le$ | $N\le$ | 特殊性質 |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | 無 |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | $200$ | $400$ | 無 |
| $7$ | $500$ | $10^3$ | A |
| $8\sim10$ | $500$ | $10^3$ | B |
| $11,12$ | $500$ | $10^3$ | 無 |
| $13$ | $3500$ | $3\times10^4$ | A |
| $14,15$ | $3500$ | $3\times10^4$ | B |
| $16\sim18$ | $3500$ | $3\times10^4$ | 無 |
| $19,20$ | $5000$ | $4\times10^4$ | 無 |
特殊性質 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\%$ 的分數。
注意：即使選手僅回答了其中一個問題，也需要按照輸出格式輸出兩個整數，分別對應兩個問題的答案。