C. Код үг

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

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

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

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

Алдарт уран барималч Цикассо Реберландын тагнуул байжээ!

Энэ нь Берландын өнөөдрийн сонинууд дээрх шуурхай мэдээ болов. Яг одоо уран барималч маань нуугдаж байгаа юм. Энэ удаад та түүнд хоргодох байр гаргаж өгөхөөр болжээ. Танд хамгаалагдсан агуулах байгаа бөгөөд үүнийг найздаа бэлдэж өгөх юм. Мөн та хамгаалалтын системийг зөвхөн та агуулахыг онгойлгож чаддаг байхаар тохируулна. Хэн нэгэн агуулахыг онгойлгохын тулд таны хувьд энгийн, бусад хүмүүсийн хувьд хүнд нэгэн бодлогыг бодож байж онгойлгодог байх юм.

Өдөр болгон агуулах нь код үг $s$-ыг үүсгэдэг. Хэн нэгэн агуулахад орохыг оролдох болгонд бүхэл тоо $n$ дэлгэцэн дээр гарч ирнэ. Хариултыг оруулахдаа тухайн хүн өөр нэгэн бүхэл тоог оруулах бөгөөд энэ нь $s$ тэмдэгт мөрийг дэд дараалал хэлбэртэй агуулах, зөвхөн Англи жижиг үсгүүдээс тогтох $n$ урт бүхий тэмдэгт мөрүүдийн тоог $10^{9} + 7$ модулаар бодсон утга байх юм.

$a$ тэмдэгт мөрийн дэд дараалал гэдэг нь уг $a$ тэмдэгт мөрөөс хэсэг тэмдэгтүүдийг авч хаях замаар (ямар ч тэмдэгт эсвэл бүх тэмдэгтийг нь ч авч хаяж болно) үүсгэж чадах $b$ тэмдэгт мөрийг хэлнэ. Тодруулбал ямар ч тэмдэгт мөр нь өөрийнхөө дэд дараалал байна. Жишээлбэл "$cfo$" тэмдэгт мөр нь "$codeforces$" гэсэн тэмдэгт мөрийн дэд дараалал байх юм.

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

Оролт

Эхний мөрөнд уг тестийн үйл явдлын тоо болох бүхэл тоо $m$ ($1 ≤ m ≤ 10^{5}$) өгөгдөнө.

2-дахь мөрөнд тухайн өдрийн агуулахын үүсгэж буй хоосон биш тэмдэгт мөр $s$ өгөгдөнө.

Дараагийн $m$ мөрөнд үйл явдлуудын тайлбар өгөгдөнө. Үйл явдлуудын тайлбар нь бүхэл тоо $t$-ээр эхлэх ба энэ нь үйл явдлын төрлийг илэрхийлнэ.

Хэрэв $t = 1$ бол шинэ өдөр болсон гэж үзэх бөгөөд агуулах шинэ $s$ тэмдэгт мөрийг үүсгэх юм. Энэ тохиолдолд уг мөрөнд шинэ $s$ тэмдэгт мөрийн утгыг өгсөн байна.

Хэрэв $t = 2$ бол бүхэл тоо $n$ $(1 ≤ n ≤ 10^{5}$) өгөгдөнө. Энэ төрлийн үйл явдал нь одоогийн $s$ тэмдэгт мөр болон $n$-ын утгын хувьд бодлогын хариултыг олох хэрэгтэй гэсэн үг юм.

Агуулахын үүсгэсэн бүх тэмдэгт мөрүүдийн уртуудын нийлбэр $10^{5}$-аас хэтрэхгүй байна. Бүх өгөгдсөн тэмдэгт мөрүүд нь зөвхөн Англи жижиг үсгүүдээс тогтсон байна.

Гаралт

$2$-р төрлийн үйл явдал болгоны хувьд хариултыг $10^{9} + 7$ модулаар бодон тусдаа мөрнүүдэд хэвлэнэ үү.

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

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

Оролт
3
a
2 2
1 bc
2 5
Гаралт
51
162626

Тэмдэглэл

Эхний үйл явдлын үгнүүд нь "$a?$" болон "$?a$" хэлбэртэйгээр тоологдох бөгөөд энд $?$ нь дурын тэмдэгт байх юм. Эдгээр 2 хэлбэрийн тус болгонд нийт $26$ үг байх боловч "$aa$" гэсэн үг нь 2-ууланд нь байх учраас хариулт нь $51$ байх юм.

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