Jalan ke Sekolah
Hitung banyaknya rute dari rumah ke sekolah yang menghindari jalan ditutup.
Kompleks rumah Sinta berbentuk kotak-kotak. Rumahnya di pojok kiri atas dan sekolahnya di pojok kanan bawah. Ia hanya berjalan ke kanan atau ke bawah, dan beberapa kotak sedang ditutup karena perbaikan jalan.
Masukan
Baris pertama berisi R dan C (keduanya 1 sampai 100). R baris berikutnya berisi peta sepanjang C karakter: . untuk kotak yang bisa dilewati dan # untuk yang ditutup.
Keluaran
Banyaknya rute berbeda, dibagi 1000000007 lalu diambil sisanya. Bila rumah atau sekolah sendiri tertutup, jawabannya 0.
Contoh masukan dan keluaran
Contoh 1
Masukan
3 3 ... .#. ...
Keluaran
2
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Banyaknya rute ke suatu kotak adalah jumlah rute ke kotak di atasnya ditambah rute ke kotak di kirinya. Kotak tertutup punya nol rute.
Petunjuk 2
Isi tabel baris demi baris dari kiri atas. Ambil sisa bagi 1000000007 setiap kali menjumlahkan supaya angkanya tidak membengkak.