Diberikan dua barisan bilangan bulat sepanjang $n$, yaitu $B=[b_1,\ldots,b_n]$ dan $C=[c_1,\ldots,c_n]$. Untuk barisan bilangan bulat nonnegatif $D=[d_1,\ldots,d_n]$ sepanjang $n$, misalkan $S(D)$ adalah himpunan semua indeks $i$ yang memenuhi $d_i=0$. Definisikan $f(D)=\sum_{i\in S(D)}b_i$ dan $g(D)=\prod_{i\in S(D)}c_i$. Secara khusus, jika $S(D)$ kosong, maka $f(D)=0$ dan $g(D)=1$.
小 L memiliki barisan bilangan bulat positif $A=[a_1,\ldots,a_n]$ sepanjang $n$. Ia dapat mengubah $A$ dengan cara berikut:
- Pilih dua indeks bersebelahan $i,j$ pada barisan $A$ (yaitu $1\le i,j\le n$ dan $|i-j|=1$). Jika $a_i\le a_j$, ubah $a_j$ menjadi $a_j-a_i$ dan secara bersamaan ubah $a_i$ menjadi $0$.
小 L boleh melakukan perubahan sebanyak apa pun, atau tidak melakukan perubahan sama sekali. Di antara semua barisan $D$ yang dapat diperoleh dari barisan $A$ dengan operasi di atas, 小 L ingin menentukan nilai maksimum $f(D)$ dan jumlah seluruh $g(D)$. Bantulah ia menghitung kedua nilai ini. Secara formal, misalkan $T(A)$ adalah himpunan semua barisan yang dapat diperoleh dari barisan $A$ melalui operasi di atas. Anda harus menghitung $\max_{D\in T(A)}f(D)$ dan $\sum_{D\in T(A)}g(D)$. Karena $\sum_{D\in T(A)}g(D)$ mungkin sangat besar, Anda hanya perlu menghitung sisanya modulo $1,000,000,007$.
Masukan
Baca data dari berkas sequence.in.
Soal ini memiliki beberapa kasus uji.
Baris pertama masukan berisi dua bilangan bulat nonnegatif $c,t$, yaitu nomor kasus penilaian dan jumlah kasus uji. $c=0$ menyatakan bahwa kasus penilaian tersebut adalah contoh.
Selanjutnya diberikan setiap kasus uji secara berurutan. Untuk setiap kasus uji:
Baris pertama berisi satu bilangan bulat positif $n$, yaitu panjang barisan.
Baris kedua berisi $n$ bilangan bulat positif $a_1,\ldots,a_n$, yang menyatakan barisan $A$.
Baris ketiga berisi $n$ bilangan bulat $b_1,\ldots,b_n$, yang menyatakan barisan $B$.
Baris keempat berisi $n$ bilangan bulat positif $c_1,\ldots,c_n$, yang menyatakan barisan $C$.
Keluaran
Tulis keluaran ke berkas sequence.out.
Untuk setiap kasus uji, keluarkan hanya satu baris berisi dua bilangan bulat, yaitu $\max_{D\in T(A)}f(D)$ dan $\sum_{D\in T(A)}g(D)$ modulo $1,000,000,007$. Perhatikan: $\max_{D\in T(A)}f(D)$ tidak perlu diambil modulo $1,000,000,007$.
Soal ini terdiri atas dua pertanyaan. Menjawab salah satunya dengan benar dapat memperoleh nilai parsial. Lihat bagian Penilaian untuk aturan lengkapnya.
Contoh
Masukan 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
Keluaran 1
15 10 1 18 37 48
Penjelasan Contoh 1
Contoh ini berisi tiga kasus uji.
Untuk kasus uji pertama, empat barisan berikut dapat diperoleh:
- $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$.
Jadi, $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$ dan $\sum_{D\in T(A)}g(D)=1+1+6+2=10$.
Contoh 2
Lihat sequence/sequence2.in dan sequence/sequence2.ans di direktori peserta.
Contoh ini memenuhi batasan kasus penilaian $3,4$.
Contoh 3
Lihat sequence/sequence3.in dan sequence/sequence3.ans di direktori peserta.
Contoh ini memenuhi batasan kasus penilaian $5,6$.
Contoh 4
Lihat sequence/sequence4.in dan sequence/sequence4.ans di direktori peserta.
Contoh ini memenuhi batasan kasus penilaian $7$.
Contoh 5
Lihat sequence/sequence5.in dan sequence/sequence5.ans di direktori peserta.
Contoh ini memenuhi batasan kasus penilaian $11,12$.
Contoh 6
Lihat sequence/sequence6.in dan sequence/sequence6.ans di direktori peserta.
Contoh ini memenuhi batasan kasus penilaian $16\sim18$.
Batasan
Misalkan $N$ adalah jumlah $n$ dari semua kasus uji dalam satu kasus penilaian. Untuk semua kasus uji, dijamin:
- $1\le t\le 20$;
- $1\le n\le 5,000$, $N\le 4\times10^4$;
- Untuk setiap $1\le i\le n$, berlaku $1\le A_i\le 10^9$;
- Untuk setiap $1\le i\le n$, berlaku $-10^9\le B_i\le 10^9$;
- Untuk setiap $1\le i\le n$, berlaku $1\le C_i\le 10^9$.
| Nomor kasus penilaian | $n\le$ | $N\le$ | Sifat khusus |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | Tidak ada |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | Tidak ada | ||
| $7$ | $500$ | $10^3$ | A |
| $8\sim10$ | B | ||
| $11,12$ | Tidak ada | ||
| $13$ | $3,500$ | $3\times10^4$ | A |
| $14,15$ | B | ||
| $16\sim18$ | Tidak ada | ||
| $19,20$ | $5,000$ | $4\times10^4$ |
Sifat khusus A: dijamin $A_1=A_2=\cdots=A_n=1$.
Sifat khusus B: dijamin untuk setiap $1\le i\le n$, $A_i$ dihasilkan secara acak seragam dan independen dari $[1,10^9]$.
Penilaian
Untuk setiap kasus penilaian:
- Menjawab $\max_{D\in T(A)}f(D)$ dengan benar untuk semua kasus uji memperoleh 40% nilai kasus penilaian tersebut;
- Menjawab $\sum_{D\in T(A)}g(D)$ modulo $1,000,000,007$ dengan benar untuk semua kasus uji memperoleh 60% nilai kasus penilaian tersebut.
Perhatikan: meskipun hanya menjawab salah satu pertanyaan, peserta tetap harus mengeluarkan dua bilangan bulat sesuai format keluaran, yang masing-masing bersesuaian dengan jawaban kedua pertanyaan.