Masala #0720
Sayr
Sakrashni yaxshi ko’radigan quyoncha bir kun \(N \times M\) jadvalning ichiga tushib qoldi. U jadvalning \((1,1)\) katagida turbid va u \((N, M)\) katakka bormoqchi. Jadvalning har bir katagi yoki oddiy yer yoki tikanakzor bo’lishi mumkin. Quyoncha bir sakrashni o’zi turgan joydan pastdagi yoki o’ngdagi eng yaqin yerga sakrashi mumkin(ya’ni tikanakzorlarni sakrab ham o’tsa bo’ladi). Quyonchani \((1,1)\) katakdan \((N,M)\) katakka yetib borish ketma-ketligining variantlar sonini toping.
Kirish faylining dastlabki satrida ikkita butun son, \(N\) va \(M (1 \le N, M \le 1000)\) sonlari kiritiladi. Keyingi qatordan boshlab \(N\) ta qatorda \(M\) tadan raqam (0 – yer, 1 – tikanakzor) kiritiladi.
Chiqish faylida yagona butun son, so’ralgan javobni \(10^9+7\) ga bo’lgandagi qoldig’ini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 3 000 011 000 |
3 |
(1,1)=>(2,1)=>(3,1)=>(3,2)=>(3,3)
(1,1)=>(1,2)=>(3,2)=>(3,3)
(1,1)=>(1,2)=>(1,3)=>(3,3)
Telegram kanalimizga obuna bo'ling