長さ $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$ の隣り合う2つの添字 $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)$ の総和を求めたいと考えています。この2つの値を求めるのを手伝ってください。形式的には、$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 からデータを読み込みます。
入力には複数のテストケースが含まれます。
最初の行に2つの非負整数 $c,t$ が与えられ、それぞれテスト番号とテストケース数を表します。$c=0$ は入出力例であることを表します。
続いて各テストケースが順に与えられます。各テストケースの形式は次のとおりです。
最初の行に正整数 $n$ が与えられ、列の長さを表します。
2行目に $n$ 個の正整数 $a_1,\ldots,a_n$ が与えられ、列 $A$ を表します。
3行目に $n$ 個の整数 $b_1,\ldots,b_n$ が与えられ、列 $B$ を表します。
4行目に $n$ 個の正整数 $c_1,\ldots,c_n$ が与えられ、列 $C$ を表します。
出力
ファイル sequence.out に出力してください。
各テストケースにつき1行に2つの整数を出力してください。それぞれ $\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$ で割った余りにする必要はありません。
この問題には2つの問いがあり、どちらか一方に正しく答えれば部分点を得られます。詳しい採点規則は「小課題」を参照してください。
入出力例
入力 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
注記
この例には3つのテストケースが含まれます。
最初のテストケースでは、次の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$ を、1つのテストに含まれるすべてのテストケースの $n$ の総和とします。すべてのテストデータについて、次が保証されます。
- $1\le t\le20$。
- $1\le n\le5\,000$、$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$ | $3\,500$ | $3\times10^4$ | A |
| $14,15$ | $3\,500$ | $3\times10^4$ | B |
| $16\sim18$ | $3\,500$ | $3\times10^4$ | なし |
| $19,20$ | $5\,000$ | $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\%$ を得られます。
注意：一方の問いだけに答える場合でも、出力形式に従い、2つの問いの答えにそれぞれ対応する2つの整数を出力する必要があります。