Gegeben sind zwei ganzzahlige Folgen $B=[b_1,\ldots,b_n]$ und $C=[c_1,\ldots,c_n]$ der Länge $n$. Für eine Folge $D=[d_1,\ldots,d_n]$ nichtnegativer ganzer Zahlen der Länge $n$ sei $S(D)$ die Menge aller Indizes $i$ mit $d_i=0$. Wir definieren $f(D)=\sum_{i\in S(D)}b_i$ und $g(D)=\prod_{i\in S(D)}c_i$. Insbesondere gilt bei leerem $S(D)$: $f(D)=0$ und $g(D)=1$.

Xiao L hat eine Folge positiver ganzer Zahlen $A=[a_1,\ldots,a_n]$ der Länge $n$. Xiao L kann $A$ wie folgt verändern:

• Wähle zwei benachbarte Indizes $i,j$ von $A$, also $1\le i,j\le n$ und $|i-j|=1$. Falls $a_i\le a_j$, ersetze $a_j$ durch $a_j-a_i$ und gleichzeitig $a_i$ durch $0$.

Xiao L darf beliebig viele Änderungsoperationen durchführen, auch gar keine. Über alle Folgen $D$, die sich aus $A$ durch diese Operationen erhalten lassen, möchte Xiao L den größten Wert von $f(D)$ sowie die Summe der Werte von $g(D)$ bestimmen. Hilf ihm, diese beiden Werte zu berechnen. Formal sei $T(A)$ die Menge aller Folgen, die sich aus $A$ durch die obigen Operationen erhalten lassen. Gesucht sind $\max_{D\in T(A)}f(D)$ und $\sum_{D\in T(A)}g(D)$. Da $\sum_{D\in T(A)}g(D)$ groß sein kann, brauchst du dafür nur das Ergebnis modulo $1\,000\,000\,007$ zu bestimmen.

Eingabe

Lies die Daten aus der Datei sequence.in.

Diese Aufgabe enthält mehrere Testfälle.

Die erste Eingabezeile enthält zwei nichtnegative ganze Zahlen $c,t$, die Testpunktnummer beziehungsweise die Anzahl der Testfälle. $c=0$ bedeutet, dass der Testpunkt ein Beispiel ist.

Es folgen der Reihe nach die Testfälle. Für jeden Testfall gilt:

Die erste Zeile enthält eine positive ganze Zahl $n$, die Länge der Folgen.

Die zweite Zeile enthält $n$ positive ganze Zahlen $a_1,\ldots,a_n$, die Folge $A$.

Die dritte Zeile enthält $n$ ganze Zahlen $b_1,\ldots,b_n$, die Folge $B$.

Die vierte Zeile enthält $n$ positive ganze Zahlen $c_1,\ldots,c_n$, die Folge $C$.

Ausgabe

Schreibe die Ausgabe in die Datei sequence.out.

Gib für jeden Testfall nur eine Zeile mit zwei ganzen Zahlen aus: $\max_{D\in T(A)}f(D)$ und $\sum_{D\in T(A)}g(D)$ modulo $1\,000\,000\,007$. Beachte: $\max_{D\in T(A)}f(D)$ wird nicht modulo $1\,000\,000\,007$ genommen.

Diese Aufgabe enthält zwei Teilfragen. Für die richtige Beantwortung einer beliebigen Teilfrage gibt es Teilpunkte. Die genauen Bewertungsregeln findest du unter „Teilaufgaben“.

Beispiele

Eingabe 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

Ausgabe 1

15 10
1 18
37 48

Hinweis

Dieses Beispiel enthält insgesamt drei Testfälle.

Für den ersten Testfall lassen sich die folgenden $4$ Folgen erhalten:

• $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$.

Daher gilt $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$ und $\sum_{D\in T(A)}g(D)=1+1+6+2=10$.

Beispiel 2

Siehe sequence/sequence2.in und sequence/sequence2.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Beschränkungen der Testpunkte $3,4$.

Beispiel 3

Siehe sequence/sequence3.in und sequence/sequence3.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Beschränkungen der Testpunkte $5,6$.

Beispiel 4

Siehe sequence/sequence4.in und sequence/sequence4.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Beschränkungen des Testpunkts $7$.

Beispiel 5

Siehe sequence/sequence5.in und sequence/sequence5.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Beschränkungen der Testpunkte $11,12$.

Beispiel 6

Siehe sequence/sequence6.in und sequence/sequence6.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Beschränkungen der Testpunkte $16$ bis $18$.

Beschränkungen

Sei $N$ die Summe der Werte von $n$ über alle Testfälle eines einzelnen Testpunkts. Für alle Testdaten ist garantiert:

• $1\le t\le 20$;
• $1\le n\le 5000$, $N\le4\times10^4$;
• Für alle $1\le i\le n$ gilt $1\le A_i\le10^9$;
• Für alle $1\le i\le n$ gilt $-10^9\le B_i\le10^9$;
• Für alle $1\le i\le n$ gilt $1\le C_i\le10^9$.

Besondere Eigenschaft A: Es ist garantiert, dass $A_1=A_2=\cdots=A_n=1$ gilt.

Besondere Eigenschaft B: Für alle $1\le i\le n$ werden die Werte $A_i$ garantiert unabhängig und gleichverteilt zufällig aus $[1,10^9]$ erzeugt.

Teilaufgaben

Für jeden Testpunkt gilt:

• Für die richtige Angabe von $\max_{D\in T(A)}f(D)$ für alle Testfälle erhältst du $40\%$ der Punkte dieses Testpunkts;
• Für die richtige Angabe von $\sum_{D\in T(A)}g(D)$ modulo $1\,000\,000\,007$ für alle Testfälle erhältst du $60\%$ der Punkte dieses Testpunkts.

Beachte: Auch wenn du nur eine der beiden Teilfragen beantwortest, musst du gemäß dem Ausgabeformat zwei ganze Zahlen ausgeben, die den Antworten auf die beiden Teilfragen entsprechen.