АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

n ширхэг англи цагаан толгойн жижиг үсгүүдээс тогтох S тэмдэгт мөр өгөгдөв.

S[i] нь S тэмдэгт мөрийн i дугаар тэмдэгтийг илэрхийлнэ. ( 0 <= i < n)

S тэмдэгт мөрийн дугаарыг илэрхийлэх дараах нөхцөлүүдийг хангах (a, b, c, d) гэсэн палиндром

дөрвөлийн дарааллыг авч үзье.

• S[a] = S[d] буюу a, d дугаарт байгаа тэмдэгтүүд ижил байна.

• S[b] = S[c] буюу b, c дугаарт байгаа тэмдэгтүүд ижил байна.

• 0 <= a < b < c < d < n буюу S тэмдэгт мөрийн индексийг илэрхийлэх a, b, c, d индексүүд өсөх дараалалтай байна.

Тэгвэл дээрх нөхцөлүүдийг хангах (a, b, c, d) дөрвөлүүдийн тоог ол.

Хариу нь маш том тоо гарч болох тул 10^9+7 тоонд хувааж үлдэгдлийг хэвлэнэ үү?

Оролтын хэлбэр 

S тэмдэгт мөр өгөгдөнө.

Хязгаарлалт 

1 <= |S| <= 10^6

S тэмдэгт мөрийн бүх үсгүүд англи цагаан толгойн жижиг үсгүүдээс тогтох нь батлагдсан.

Гаралтын хэлбэр 

Бодлогын нөхцөлийг хангах дөрвөлүүдийн тоог хэвлэнэ. Хариу маш том тоо гарч болох тул

10^9+7 тоонд хуваасан үлдэгдлийг /модульдаж/ хэвлэнэ.

Жишээ

Оролт 1

kkkkkkz

Гаралт 1

15

Тайлбар 1

Бодлогын нөхцөлийг ядаж хамгийн багадаа 2 ижил байх тэмдэгт хангах тул z үсэг дөрвөлийн нэг болж

чадахгүй учир тэдгээр дөрвөл нь k –уудаас тогтох нь илэрхий байна.

Тэгвэл 6 ширхэг к-аас 4-ийг сонгох боломжийн тоог олох хэрэгтэй болж байгаа бөгөөд энэ нь 15 байна.

Оролт 2

ghhggh

Гаралт 2

4

Тайлбар 2

Тэдгээр дөрвөлүүд нь:

Тиймээс хариу нь 4 mod (10^9+7) = 4

Оролт 3

akakak

Гаралт 3

2

Тайлбар 3

Тэдгээр дөрвөлүүд нь  (1, 2, 4, 5) ба (0, 1, 3, 4)