Masala #0597
Labirintdagi yo'llar soni.
Sizga \(N*M\) 0 va 1 lardan iborat labirint beriladi. labirintda eshigi ochiq(0) va yopiq(1) xonalar mavjud.
Bu labirintda siz quyidagi amallarni bajarishngiz mumkin.
1.Labirintning satrdagi keyingi eshigi ochiq bo'lgan xonaga o'tishingiz mumkin.
2.Labirintning ustunidagi keyingi eshigi ochiq bo'lgan xonaga o'tishingiz mumkin.
Ushbu amallarni bajargan holda labirintning \((1,1)\) xonasidan \((N,M)\) xonasiga borishning usullar soni hisoblang.
1-qatorda \(N\) va \(M\) \((1 \le N,M \le 1000)\).
\(N\) ta ustunda xonalardan iborat uzunligi \(M\) ga teng satrlar.
\((N,M)\) xonaga borish usullar sonini \(10^9+7\) ga bo'lgandagi qoldiq.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 3 000 011 000 |
3 |
000
011
000 bu labirint uchun yo'llar soni.
\(1. (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)\)
\(2. (1,1) -> (1,2) -> (3,2) -> (3,3)\)
\(3. (1,1) -> (1,2) -> (1,3) -> (3,3)\)
Telegram kanalimizga obuna bo'ling