C. Тэнцвэржсэн тэмдэгт мөр

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

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

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

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

Ник тэмдэгт мөрөнд их дуртай ба тэдгээрийг эргүүлэх, эрэмбэлэх, тэмдэгтүүдийн байрыг солих их дуртай. Нэгэн удаа тэрээр $a$, $b$, $c$ үсгүүдээс тогтох дурын тэмдэгт мөр бичин, дараах үйлдлүүдийг хийж эхэлжээ:

  • Хөрш хоёр тэмдэгтийг авч үзэн хоёр дахь тэмдэгтийг эхнийхээр нь солих.
  • Хөрш хоёр тэмдэгтийг авч үзэн эхний тэмдэгтийг хоёр дахиар нь солих.

Энэ үйлдлийг ойлгохын тулд "abc" тэмдэгт мөрийг авч үзье. Нэг үйлдлээр "bbc", "abb", "acc" тэмдэгт мөрүүд гарч ирж чадна. "a", "b", "c" тэмдэгт бүрийн давтамж гэдгээр тухайн тэмдэгт мөрөнд оролцож буй тоог тэмдэглэе. Жишээ нь "abc" тэмдэгт мөрийн хувьд: |a| = 1, |b| = 1, |c| = 1, ба "bbc" тэмдэгт мөрийн хувьд: |a| = 0, |b| = 2, |c| = 1 байна.

Ник үйлдлүүдийг гүйцэтгэх явцдаа заримдаа тэнцвэржсэн тэмдэгт мөр гаргаж авч байв. Хэрэв тэмдэгт бүрийн давтамжийн зөрүү нь 1-ээс хэтрэхгүй бол тухайн тэмдэгт мөрийг тэнцвэржсэн тэмдэгт мөр гэнэ. ($-1 ≤ |a|-|b| ≤ 1$, $-1 ≤ |a|-|c| ≤ 1$, $-1 ≤ |b| - |c| ≤ 1$)

Өгөгдсөн $s$ тэмдэгт мөрөнд дээрх үйлдлүүдийг давтан хийсээр хичнээн ялгаатай тэнцвэржсэн тэмдэгт мөр гаргаж болохыг олоход туслаарай. Хариуг $51123987$-д хуваан гарах үлдэгдлийг олоорой.

Оролт

Эхний мөрөнд $s$ тэмдэгт мөрийн урт болох $n$ ($1 ≤ n ≤ 150$) бүхэл тоо байна. Анхны тэмдэгт мөр мөн тэнцвэржсэн тэмдэгт мөр байж болно. Энэ тохиолдолд анхны тэмдэгт мөрийг мөн тоолно. Өгөгдсөн тэмдэгт мөр $s$ зөвхөн "a", "b", "c" тэмдэгтүүдээс тогтоно.

Гаралт

Үйлдлүүдийг гүйцэтгэх замаар гаргаж чадах тэнцвэржсэн тэмдэгт мөр-ийн тоог $51123987$ тоонд хуваан үлдэгдлийг хэвлэнэ үү.

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

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

Оролт
4
abca
Гаралт
7
Оролт
4
abbc
Гаралт
3
Оролт
2
ab
Гаралт
1

Тэмдэглэл

Эхний жишээнд үйлдлүүдийг гүйцэтгэх замаар $51$ ялгаатай тэмдэгт мөр гарч ирж болохын $7$ нь тэнцвэржсэн тэмдэгт мөр байна: "abca", "bbca", "bcca", "bcaa", "abcc", "abbc", "aabc".

Хоёр дахь жишээнд: "abbc", "aabc", "abcc".

Гурав дахь жишээнд ганцхан "ab" (өөрөө) гэсэн тэнцвэржсэн тэмдэгт мөр гарч ирэх боломжтой.

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