D. Яст мэлхий

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n \times m$ хүснэгт өгөгджээ. Мөрүүд нь дээрээс доош $1$-с $n$ хүртэл дугаарлагдсан ба баганууд нь зүүнээс баруун тийшээ $1$-с $m$ хүртэл дугаарлагджээ. Тэгээд бид $x$ мөрний $y$ багана дахь нүдийг $(x,y)$ гэж тэмдэглэе.

Анхлан $(1,1)$ нүдэнд 2 төстэй яст мэлхий байна. Аль аль нь $(n,m)$ нүдэнд очихыг хүсч буй. Зарим нь нүднүүд саадтай боловч зүүн дээд, баруун доод булангууд саадгүй гэдэг нь мэдэгдэж байв. Яст мэлхийнүүд $(x,y)$ нүднээс $(x+1,y), (x,y+1)$ нүднүүд рүү очиж чадна. (энэ нүднүүд саад агуулаагүй үед л ингэж шилжиж чадна.) Яст мэлхийнүүд хоорондоо таарамжгүй байгаа тул замдаа таарахгүй байхыг хүсчээ. Тэгвэл тэдэнд тусалж $(1,1)$нүднээс $ (n,m)$ нүд рүү хэдэн янзаар очиж чадахыг олно уу.

(1, 1) нүднээс (n, m) нүд рүү үл огтлолцох хос замын тоог $1000000007 (10^9+7)$ тоонд хувааж үлдэгдлийг нь хэвлэнэ үү. 2 яст мэлхийний зам эхлэл төгсгөлөөс өөр ерөнхий цэггүй бол энэ 2 замыг үл огтлолцох хос зам гэнэ.

Оролт

Эхний мөрөнд $n, m (2\le n,m\le 3000)$ тоонууд өгөгдөнө. Дараагийн $n$ мөр бүр хүснэгтийг тодорхойлох $m$ тэмдэгт агуулна. Хоосон мөрүүд "."-р тэмдэглэгдэх бол саадтай мөрнүүд "#" байна.

Зүүн дээд, баруун доод нүднүүд хоосон байна.

Гаралт

$(1,1)$-с $(n,m)$ хүрэх үл огтлолцох хос замын тоог $1000000007 (10^9+7)$ модулиар жишч хэвлэ.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
4 5
.....
.###.
.###.
.....
Гаралт
1
Оролт
2 3
...
...
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...