Perkalian Matriks Bebek (6B)

Perkalian Matriks Bebek

Batas Waktu

1 detik
Batas Memori	 64 MB
Sebanyak N ekor bebek Pak Dengklek yang bersahabat bernomor 1 hingga N berbaris urut sesuai nomor mereka dengan urutan menaik. Masing-masing bebek i (1 ≤ i ≤ N) diberi sebuah papan yang berisi Matriks berukuran Ri x Ci di mana untuk setiap bebek yang berdampingan, kolom Matriks bebek bernomor lebih kecil sama dengan baris Matrix bebek bernomor lebih besar.

Sekarang, gajah-gajah Pak Ganesh diminta untuk menghitung hasil kali N buah Matriks tersebut. Namun, gajah-gajah sangat pintar. Mereka bisa menghitung hasil kali tersebut dengan sesedikit mungkin langkah. Banyaknya langkah mengalikan dua buah Matriks berukuran a x b dengan b x c adalah sebesar a x b x c. Perkalian gajah-gajah itu akan membentuk suatu string ekspresi akhir E yang merupakan pola ekspresi awal yang ditampilkan para bebek dengan diberi tanda-tanda kurung sesuai dengan urutan perkalian Matriks yang dilakukan oleh gajah (setiap kali gajah mengalikan dua buah Matriks, dia memberikan kurung).

Buatlah sebuah program yang akan menjawab salah satu dari tiga pertanyaan yang diajukan gajah-gajah berikut:

Berapa total langkah yang dilakukan gajah Pak Ganesh dalam mengalikan matriks-matriks tersebut?

Berapakah sisa pembagian jumlah cara membentuk E yang menghasilkan langkah optimal dengan sebuah bilangan bulat 26101991?

Berapakan sisa pembagian jumlah cara membentuk E di mana langkahnya tidak harus optimal (dua ekspresi akhir dikatakan berbeda jika kedua string yang dihasilkan berbeda) dengan sebuah bilangan bulat 26101991?



Format Masukan

Baris 1 berisi satu buah bilangan bulat N (1 ≤ N ≤ 100).

Baris 2 berisi N + 1 buah bilangan, di mana bilangan ke-i (2 ≤ i ≤ N - 1) merupakan kolom dari Matriks ke-(i - 1) dan baris dari Matriks ke-i. Dan bilangan pertama merupakan baris dari Matriks pertama, dan bilangan terakhir merupakan kolom dari Matriks terakhir.

Baris 3 berisi sebuah bilangan bulat Q (1 ≤ Q ≤ 3) yang menyatakan pertanyaan yang diajukan Pak Dengklek (Pak Dengklek bertanya pertanyaan nomor Q).

Format Keluaran

Untuk setiap jenis pertanyaan, outputkan sebuah bilangan bulat yang merupakan jawaban dari pertanyaan tersebut.

Contoh Masukan

4
1 2 3 4 5
1
Contoh Keluaran

38
Contoh Masukan

4
1 2 3 4 5
2
Contoh Keluaran

1
Contoh Masukan

4
1 2 3 4 5
3
Contoh Keluaran

5
Penjelasan

Ada 5 kemungkinan perkalian Matriks tersebut:

(((A1xA2)xA3)xA4)

((A1xA2)x(A3xA4))

((A1x(A2xA3))xA4)

(A1x((A2xA3)xA4))

(A1x(A2x(A3xA4)))

Di mana solusi optimalnya adalah kemungkinan pertama dengan jumlah langkah 1 x 2 x 3 + 1 x 3 x 4 + 1 x 4 x 5 = 38.
Peringatan

Output selalu dalam batas signed integer 64 bit.