RoboContest

Xotira 20 MB Vaqt 1000 ms

14

Muallif: Shahzod

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.

Kiruvchi ma'lumotlar:

1-qatorda $N$ va $M$ $(1 \le N,M \le 1000)$ .

$N$ ta ustunda xonalardan iborat uzunligi $M$ ga teng satrlar.

Chiquvchi ma'lumotlar:

$(N,M)$ xonaga borish usullar sonini $10^9+7$ ga bo'lgandagi qoldiq.

Misollar

#	input.txt	output.txt
1	3 3 000 011 000	3

Izoh:

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)$