Qaya rəsmləri#10439
Bessi rəssam oldu və mağara mənzərələri çəkir! İndi o, hündürlüyü olan, hər sətrində düz xana olan bir şəbəkəni təsvir edən bir mənzərə üzərində işləyir. Hər xana ya boşdur, ya daşla doludur, ya da su ilə doludur. Bessi artıq daş olan bütün xanaları, o cümlədən mənzərənin bütün sərhədini boyayıb. İndi o, bəzi boş xanaları su ilə elə doldurmaq istəyir ki, əgər mənzərə həqiqi bir mağara olsaydı, suyun ümumi hərəkəti baş verməsin.
Yuxarıdan -ci sətirdə yerləşən xananın hündürlüyünü n + 1 - i kimi təyin edək. Bessi mənzərəsinin aşağıdakı şərtə cavab verməsini istəyir:
Fərz edək ki, xanası su ilə doludur. Əgər -dan xanasına yalnız hündürlüyü xanasının hündürlüyündən artıq olmayan boş xanalar və ya su ilə dolu xanalardan keçən, və yolun hər iki qonşu xanası ümumi tərəfə malik olan bir yol varsa, onda xanası da su ilə dolu olmalıdır.
Bessinin yarada biləcəyi fərqli mənzərələrin sayını 10^9 + 7 modulu ilə tapın. Bessi istənilən sayda boş xananı — heç birini və ya hamısını da daxil olmaqla — su ilə doldura bilər.
Birinci sətirdə iki tam ədəd və m~(1 \le n, m \le 1000) verilir.
Sonrakı sətirin hər birində simvol verilir. Hər simvol ya '', ya da '#' olur və müvafiq olaraq boş xananı və daşla dolu xananı bildirir. Birinci və sonuncu sətirlər, eləcə də birinci və sonuncu sütunlar yalnız '#' simvollarından ibarətdir.
Şərtə cavab verən mənzərələrin sayını 10^9 + 7 modulu ilə bir tam ədəd olaraq çap edin.
Əgər ikinci sətirdəki istənilən xana su ilə doludursa, onda bütün boş xanalar da su ilə dolu olmalıdır. Əks halda, fərz edək ki, ikinci sətirdə heç bir xana su ilə dolu deyil. Onda Bessi üçüncü sətirdəki üfüqi bağlı boş xana bölgələrinin hər birini müstəqil şəkildə su ilə doldurub-doldurmamağı seçə bilər. Beləliklə, mənzərələrin ümumi sayı 1 + 2^3 = 9 olur.
Nümunə 1