C. Генийн эгнээ

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

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

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

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

Вася био-информатикт сонирхолтой болжээ. Тэрээр цикл бүтэцтэй Генийн дарааллын ижил төстэй чанаруудын талаар нийтлэл бичихээр ажиллаж байгаа. Тэгээд цикл дарааллуудыг төсөөтэй эсэхийг шалгах шинэ арга зохиожээ.

$s$ болон $t$ нь ижилхэн $n$ урттай тэмдэгт мөрүүд байг. Тэгвэл $h(s, t)$ функц нь $s$ болон $t$ тэмдэгт мөрүүдэд хэдэн тэмдэгт байрлал болон утгаараа давхцаж байгааг илэрхийлнэ. $h(s, t)$ функц нь Васягийн зайн функц болох $ρ(s, t)$-г тодорхойлно:

$$ p(s, t) = \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{n-1} h(shift(s, i),\ shift(t, j)) $$

Энд $shift(s, i)$ нь $s$ тэмдэгт мөрийг зүүн тийш $i$ тэмдэгтээр зөөхөд (тэмдэгт мөр цикл бүтэцтэй учир сүүлийн тэмдэгт эхэндээ ирнэ) гарах тэмдэгт мөр юм. Жишээ нь:

$ρ$("AGC", "CGT") = $h$("AGC", "CGT") + $h$("AGC", "GTC") + $h$("AGC", "TCG") + $h$("GCA", "CGT") + $h$("GCA", "GTC") + $h$("GCA", "TCG") + $h$("CAG", "CGT") + $h$("CAG", "GTC") + $h$("CAG", "TCG") = $1 + 1 + 0 + 0 + 1 + 1 + 1 + 0 + 1 = 6$

Вася интернетээс $n$ урттай $s$ гэсэн тэмдэгт мөр олжээ. Одоо тэрээр өөрийн зайн функц-д $s$ тэмдэгт мөрийн хувьд боломжит хамгийн их утгыг буцаадаг $t$ тэмдэгт мөрийн тоог мэдэхийг хүсжээ. Өөрөөр хэлбэл $t$ дараахь тэгшитгэлийг хангах ёстой: $p(s, t) = \max\limits_{u:|u|=|s|} p(s, u)$.

Вася бүх боломжит тэмдэгт мөрийг шалгаж чадахгүй тул чамаас тусламж хүсчээ. Хариу хэтэрхий том тоо байж болох тул нөхцөлийг хангах тэмдэгт мөрийн тоог $10^{9} + 7$ тоонд хуваан үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 10^{5}$) тоо өгөгдөнө.

Хоёр дахь мөрөнд $n$ урттай "ACGT" тэмдэгтүүдээс тогтох тэмдэгт мөр өгөгдөнө.

Гаралт

Хариуг $10^{9} + 7$ тоонд хуваан үлдэгдлийг хэвлэ.

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

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

Оролт
1
C
Гаралт
1
Оролт
2
AG
Гаралт
4
Оролт
3
TTT
Гаралт
1

Тэмдэглэл

$t_{1}$ ба $t_{2}$ гэсэн ялгаатай тэмдэгт мөрүүдийн хувьд $ρ(s, t_{1})$ ба $ρ(s, t_{2})$ утгууд хоёулаа боломжит $t$-үүдийн хувьд максимум утга авч чадаж байвал хэдий нэгнийг нь эргүүлэх замаар нөгөөг нь гаргаж авч чаддаг байсан ч хоёуланг нь нөхцөл хангах тэмдэгт мөр мөн гэж тооцно.

Эхний жишээнд $ρ$("C", "C") $= 1$ ба үлдсэн $1$ урттай тэмдэгт мөрүүдийн хувьд $ρ(s, t) = 0$ байна.

Хоёр дахь жишээнд $ρ$("AG", "AG") = $ρ$("AG", "GA") = $ρ$("AG", "AA") = $ρ$("AG", "GG") $= 4$

Гурав дахь жишээнд $ρ$("TTT", "TTT") $= 27$

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