D. Палиндром зэрэг

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

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

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

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

$n$ урттай, палиндром $s$ тэмдэгт мөрийн $n/2$ урттай салгасан 2 дэд тэмдэгт мөр нь $k-1$ -р зэргийн палиндром байвал $s$ тэмдэгт мөрийг $k$-р зэргийн палиндром гэе.

Мөн $s$ тэмдэгт мөрийг хамгийн их $k$ зэргээр нь үнэлж, $k$-р зэргийн палиндром гэе. Жишээ нь "abaaba" нь $3$-р зэргийнх болно.

Танд тэмдэгт мөр өгөгдсөн бол энэ тэмдэгт мөрийн бүх угтварынх нь зэргийн нийлбэрийг олно уу.

Оролт

Оролтонд латин цагаан толгойн том ба жижиг үсэг болон тооноос тогтох хоосон биш тэмдэгт мөр өгөгдөнө. Тэмдэгт мөрийн урт $5·10^6$-с хэтрэхгүй.

Гаралт

Тэмдэгт мөрийн бүх угтварын зэргийн нийлбэр болох ганц тоог хэвлэнэ.

Орчуулсан: zoloogg

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

Оролт
a2A
Гаралт
1
Оролт
abacaba
Гаралт
6
Сэтгэгдлүүдийг ачааллаж байна...