Palindromik Yollar (Gold)#11174

Palindromik Yollar (Gold)

2 saniyə

128 meqabayt

Çətin

Farmer Con-un fermasi n × n ölçülü xanalardan ibarət şəbəkədir və hər xana əlifbadan bir hərf saxlayır. Məsələn:

ABCD
BXZX
CDXB
WCBA

Hər gün Bessie adlı inək yuxarı-sol xanadan aşağı-sağ xanaya qədər gedir. Hər addımda o, ya bir xana sağa, ya da bir xana aşağı hərəkət edir. Gedərkən, Bessie ziyarət etdiyi xanaların hərflərindən yaranan sətri qeyd edir.

Ancaq əgər yaranan sətir palindromdursa (yəni, irəli və geri oxunduqda eyni olursa), Bessie çox çaşır, çünki artıq hansı istiqamətdə getdiyini xatırlaya bilmir.

Zəhmət olmasa, Bessie-yə palindromik sətir yaradan fərqli marşrutların sayını müəyyən etməkdə kömək edin. Eyni palindromu yaradan fərqli marşrutlar ayrı-ayrılıqda hesablanmalıdır.

Cavabı modulo $1 0^{9} + 7$ 10^9 + 7 ilə çap edin.

Giriş

Birinci sətirdə bir tam ədəd $n (1 \leq n \leq 500)$ n~(1 \le n \le 500) verilir.

Növbəti $n$ sətirdə şəbəkənin $n$ sətri verilir. Hər sətir A-dan Z-yə qədər böyük hərflərdən ibarət $n$ hərfdən ibarətdir.

Çıxış

Yuxarı-sol xanadan aşağı-sağ xanaya qədər olan və nəticədə yaranan sətri palindrom olan marşrutların sayını modulo $1 0^{9} + 7$ 10^9 + 7 ilə çap edin.

Nümunələr

Bessie aşağıdakı palindromları yarada bilər:

1 x "ABCDCBA"
1 x "ABCWCBA"
6 x "ABXZXBA"
4 x "ABXDXBA"

Nümunə 1