C. Шифр

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

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

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

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

Шерлок Холмес 2 VIP-ын нэгэн нууцлаг захиа олсон бөгөөд уг захиаг уншихын тулд нэлээн ухаан сийлжээ. Гэвч нэгэн асуудал байлаа! Уг захиа нь шифрлэгдсэн болж таарав. Мөрдөгч уг захианы шифрийг тайлах гэж үнэхээр их хичээсэн боловч тэрээр юу ч ойлгохгүй байв.

Эцэст нь нэлээн бодсоны эцэст тэрээр нэгэн зүйлийг бодож олов. $|s|$ ширхэг Латин жижиг үсгүүдээс тогтох $s$ гэсэн үг байна гэж үзье. Тэгвэл бид $p$ ($1 ≤ p < |s|$) гэсэн нэгэн байрлалыг сонгож дараах үйлдлүүдийн нэгийг гүйцэтгэж болох байв:

  • $s_{p}$ үсгийг цагаан толгойн дарааллынх нь дараагийн үсгээр солих ба $s_{p + 1}$ үсгийг цагаан толгойн дарааллынх нь өмнөх үсгээр солино;
  • эсвэл $s_{p}$ үсгийг цагаан толгойн дарааллынх нь өмнөх үсгээр солих ба $s_{p + 1}$ үсгийг цагаан толгойн дарааллынх нь дараагийн үсгээр солино.

Түүнчлэн "$z$" үсгийн хувьд цагаан толгой дарааллынх нь дагуу дараагийн үсэг гэж байхгүй бөгөөд "$a$" үсгийн хувьд өмнөх үсэг гэж байхгүй байх юм. Ийм учраас эдгээр өөрчлөлтүүдийг хийж болохгүй байна. Хэрэв ямар нэгэн үйлдэл дээр дор хаяж нэг ширхэг хийж болохгүй үйлдэл хийхийг шаардаж байвал уг үйлдлийг гүйцэтгэж болохгүй байх юм.

Хэрэв 2 үгийн хувьд 0 эсвэл илүү олон тооны үйлдэл хийсний үр дүнд аль нэг нь нөгөө үг уруугаа хувирч чаддаг байвал эдгээр үгнүүдийг утгаараа ижил байна гэж үзнэ.

Шерлок Холмес үг бүрийн хувьд дараах зүйлийг маш хурдан тодорхойлж сурах хэрэгтэй болжээ: өгөгдсөн үгтэй утгаараа ижил боловч дор хаяж нэг ялгаатай тэмдэгт агуулсан байх хэчнээн тооны үг оршин байх вэ? Уг тоог түүнд туслан $1000000007$ $(10^{9} + 7)$ модулаар бодон олж өгнө үү.

Оролт

Оролтын өгөгдөл нь хэд хэдэн тест агуулна. Эхний мөрөнд бүхэл тоо $t$ ($1 ≤ t ≤ 10^{4}$) өгөгдөх ба энэ нь тестийн тоог илэрхийлнэ.

Дараагийн $t$ ширхэг мөрүүдийн мөр болгонд нэг үгийг дүрсэлнэ. Үг болгон нь Латин жижиг үсгүүдээс тогтох бөгөөд $1$-ээс $100$ хүртэлх (эдгээр нь өөрсдөө орно) тэмдэгт бүхий урттай байна. Үгнүүдийн уртууд нь ялгаатай байж болно.

Гаралт

Үг бүрийн хувьд уг үгтэй утгаараа ижил байх бусад ялгаатай үгүүдийн тоог хэвлэх бөгөөд та эдгээр оролтод өгөгдсөн үгүүд дундаас биш бүх боломжит үгүүд дундаас тухайн үгтэй ижил утгатай үгсийн тоог олох юм. Бидний хайж буй тоо нь маш том тоо байж болох учраас уг тооны утгыг $1000000007$ $(10^{9} + 7)$ модулаар бодон хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
1
ab
Гаралт
1
Оролт
1
aaaaaaaaaaa
Гаралт
0
Оролт
2
ya
klmbfxzb
Гаралт
24
320092793

Тэмдэглэл

Үйлдлийн тухайн зарим тайлбарууд доор өгөгдөв:

  • Үсэг болгоны хувьд бид уг үсгийн дараах үсгийг тодорхойлж чадна. "$b$" үсэг нь "$a$"-ын дараах үсэг бөгөөд "$c$" нь "$b$"-ын дараах, ..., "$z$" нь "$y$"-ын дараах үсэг байх юм.
  • Өмнөх үсгүүд нь мөн ижил байдлаар тодорхойлогдоно: "$y$" нь "$z$"-ын өмнөх үсэг, ..., "$a$" нь "$b$"-ын өмнөх үсэг байх юм.
  • Мөн уг үйлдэл нь хэзээ ч үгийн уртыг өөрчлөхгүй болохыг анхаарна уу.

Эхний жишээнд та зөвхөн "$ba$" гэсэн үгийг гарган авч чадна. 2-дахь жишээнд та ямар ч үг гарган авч чадахгүй бөгөөд иймд зөв хариулт нь $0$ болох юм.

3-дахь жишээг авч үзье. Та нэг үйлдлээр "$klmbfxzb$" гэсэн үгийг "$klmcexzb$" гэсэн үг болгож чадна: та ингэхийн тулд $p = 4$ гэж сонгох ёстой ба 4-р үсгийг дараагийн үсгээр нь ("$b$" $ -> $ "$c$") 5-р үсгийг өмнөх үсгээр нь ("$f$" $ -> $ "$e$") солих юм. Мөн бид уг үгээс маш олон тооны үгийг гарган авч болно. Та нэг үйлдлээр "$ya$" гэсэн үгийг зөвхөн $xb$" гэсэн үг уруу хувиргаж чадахыг анхаарна уу.

"$ya$" гэсэн үг нь утгаараа "$xb$", "$wc$", "$vd$", ..., "$ay$" (нийтдээ $24$ өөр үг байна) гэсэн үгстэй ижил байх юм. "$klmbfxzb$ гэсэн үг нь өөр маш олон хувилбартай байх бөгөөд тодруулбал $3320092814$ ширхэг ижил утга бүхий үгс оршин байх юм. Иймд эхний үгийн хувьд хариулт нь $24$-тэй тэнцүү байх бөгөөд 2-дахь үгийн хувьд хариулт нь $320092793$ буюу $3320092814$-ыг $10^{9} + 7$ модулаар бодсон утга байх юм.

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