E. Гахай ба палиндром

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

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

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

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

Пэппа гахай ойгоор зугаалж явжээ. Их сонин тохиолдлоор ой мод $n$ мөр болон $m$ баганатай тэгш өнцөгт хэлбэртэй ажээ. Бид тэгш өнцөгтийн мөрүүдийг дээрээс нь доош $1$-ээс $n$ хүртэл, багануудыг зүүнээс баруун тийш $1$-ээс $m$ хүртэл дугаарласан. $r$ дугаарын мөр болон $c$ дугаарын баганын огтлолцолд буй нүдний координатыг $(r, c)$ гэж тэмдэглэе.

Эхлээд гахай $(1, 1)$ нүдэн дээр зогсож байгаа ба $(n, m)$ нүдэнд хүрэхийг зорьж байгаа. Гахай ихэд яарч байгаа тул $(r, c)$ нүднээс зөвхөн $(r + 1, c)$ эсвэл $(r, c + 1)$ нүд рүү л шилжих боломжтой. Мөн тэрээр ойгоос гарч болохгүй.

Гахайн зугаалж буй ой их өвөрмөц. Ойн зарим нүднүүд хоорондоо их төстэй. Пэппа зураг авах дуртай тул очсон нүд бүрийхээ зургийг авч байжээ. Ойгоор зугаалсан зураг дарааллаараа хойноос нь уншсантай ижил байвал тухайн зугаалсан замыг үзэсгэлэнтэй гэж нэрлэнэ. Өөрөөр хэлбэл очсон нүднүүдийн зургийг дарааллаар нь нэг шулуунд эгнүүлэн тавихад палиндром байвал уг замыг үзэсгэлэнтэй гэх юм.

$(1, 1)$ нүднээс $(n, m)$ хүрэх үзэсгэлэнтэй замын тоог олно уу. Хариу их том байж болох тул $10^{9} + 7$-д хуваан үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд ойн урт болон өргөнийг илэрхийлэх $n, m$ ($1 ≤ n, m ≤ 500$) бүхэл тоонууд байна.

Дараагийн $n$ мөр бүрт $m$ ширхэг Англи цагаан толгойн жижиг үсэг байх ба эдгээр нь ойн нүднүүдийн төрлийг илэрхийлнэ. Хоорондоо ижил нүднүүд ижил үсгээр, харин ялгаатай нүднүүд ялгаатай үсгээр тэмдэглэгдэнэ.

Гаралт

Үзэсгэлэнтэй замын тоог $10^{9} + 7$ тоонд хуваан үлдэгдлийг хэвлэнэ үү.

Орчуулсан: Бат-Од

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

Оролт
3 4
aaab
baaa
abba
Гаралт
3

Тэмдэглэл

Жишээг зургаар дүрсэлбэл:

Сэтгэгдлүүдийг ачааллаж байна...