Deskripsi Untuk Soal Nomor 27 dan 30
DESKRIPSI CERITA
Pak Dengklek mempunyai lapangan yang terdiri dari N baris dan M kolom petak-petak persegi. Barisnya dinomori dari 1 sampai N, sedangkan kolomnya dinomori dari 1 sampai M. Petak yang berada di baris ke-i dan kolom ke-j dinotasikan dengan (i, j) dan mempunyai nilai A[i][j] (untuk semua 1 ≤ i ≤ N, 1 ≤ j ≤ M). Pak Dengklek dapat melompat dari (i, j) ke (i', j') jika dan hanya jika semua persyaratan berikut ini terpenuhi:
Jadi, jika A[i][j] = 0, maka Pak Dengklek tidak akan bisa melompat ke petak mana pun dari petak (i, j). Pak Dengklek bertanya-tanya, ada berapakah banyaknya urutan lompatan berbeda untuk bergerak dari (1, 1) ke (N, M). Dapatkah Anda membantu Pak Dengklek menjawab pertanyaan tersebut? Karena jawabannya bisa sangat besar, keluarkan jawabannya modulo 1 000 000 007.
Diketahui petak berukuran 3 x 4 dengan isi sebagai berikut:
| 3 | 1 | 0 | 4 |
| 2 | 0 | 0 | 1 |
| 4 | 1 | 3 | 2 |
Dapatkah Pak Dengklek bergerak dari petak (2, 4) ke petak (1, 2)?
Jawaban: ............... {tuliskan jawaban dalam bentuk YA/TIDAK}
Diketahui petak berukuran 3 x 4 dengan isi sebagai berikut:
| 3 | 1 | 0 | 4 |
| 2 | 0 | 0 | 1 |
| 4 | 1 | 3 | 2 |
Dapatkah Pak Dengklek bergerak dari petak (1, 2) ke petak (3, 4)?
Jawaban: ............... {tuliskan jawaban dalam bentuk YA/TIDAK}
Diketahui petak berukuran 3 x 4 dengan isi sebagai berikut:
| 3 | 1 | 0 | 4 |
| 2 | 0 | 0 | 1 |
| 4 | 1 | 3 | 2 |
Ada berapa banyak cara bagi Pak Dengklek untuk bergerak dari (1,1) ke (3, 4)?
Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}
Buatlah sebuah program dalam Bahasa C/C++ untuk menjawab pertanyaan Pak Dengklek sesuai dengan deskripsi pada cerita di atas!
Format Masukan:
Baris pertama berisi dua buah bilangan N dan M yang menyatakan ukuran petak yang dimiliki pak Dengklek (N = banyaknya baris, M = banyaknya kolom). N buah baris berikutnya masing-masing berisi M buah bilangan bulat non-negatif yang masing-masing terpisahkan dengan sebuah spasi. Setiap bilangan pada baris ke-i dan kolom ke-j menyatakan nilai A[i][j] (untuk semua 1 ≤ i ≤ N, 1 ≤ j ≤ M).
Format Keluaran:
Sebuah baris yang berisi sebuah bilangan K yang menyatakan banyaknya cara Pak Dengklek bergerak dari petak (1,1) ke petak (N, M) sesuai dengan aturan di atas, modulo 1 000 000 007.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
2 3 2 0 1 1 1 3 | 4 |
Penjelasan Contoh:
Ada 4 urutan lompatan berbeda untuk bergerak dari (1, 1) ke (2, 3) pada contoh petak di atas, yaitu:
Batasan:
Untuk semua kasus uji berlaku:
Untuk 50% kasus uji berlaku:
Masuk untuk menulis jawaban