Masala #A7FSXYFIU9

Xotira 32 MB Vaqt 1000 ms

Yo'llar soni

Sizga N soni va NxN tomonli labirint xaritasi beriladi. Labirintda tuzoqlar bo'lishi mumkin. Siz tuzoqli katakka yura olmaysiz.

Siz labirintning chap-tepa katagidan boshlab past-o'ng katakka borishning nechi xil usuli borligini topishingiz kerak. Siz faqat o'ngga va pastga harakatlana olasiz.

Kiruvchi ma'lumotlar:

1 - qatorda N soni kiritiladi \(1<=N<=10^3\)

Keyingi N ta qatorda NxN matritsa kiritiladi.

Chiquvchi ma'lumotlar:

Masala javobini \(10^9+7\)ga bo'lgandagi qoldiqni chiqaring.

Misollar

#	input.txt	output.txt
1	4 .... ... ... *...	3

Izoh:

Agar xarita[i][j] ‘.’ ga teng bo'lsa yursa bo'ladigan joyni bildiradi, ‘*’ esa tuzoq joylashgan katakni anglatadi.