C. Генетик инженерчлэл

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

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

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

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

"Генетикийн асуудлуудаас ялгаатай нь олон хэмжээст огторгуйнууд нь өнөө үед нэг их чухалд тооцогдохоо байжээ" хэмээн Физикч Волл бодох бөгөөд үүний зэрэгцээгээр өөрийн сурах хичээлээ биоинформатик-ийн хичээлээр сольжээ. Дарааллын үр дүнг судалсны дараа тэрээр дараах DNA дарааллын талаар өгүүлэх бодлоготой тулгарчээ. Бид үүнээс цааш DNA дарааллыг "A", "C", "G" болон "T" гэсэн том үсгүүдээс тогтох дурын тэмдэгт мөр гэж үзэх болно (мэдээж хэрэг энэ бол хялбарчилсан илэрхийлэл юм).

$w$ нь нэгэн урт DNA дараалал бөгөөд $s_{1}, s_{2}, ..., s_{m}$ нь богино DNA дарааллуудын цуглуулга гэж үзье. Хэрэв $w$ нь цуглуулга доторх дарааллуудаар хучигдаж байвал уг цуглуулга нь $w$-г шүүж байна гэж үзэх юм. Мэдээж хэрэг тэмдэгт мөрийн ялгаатай байрлалд харгалзаж буй дэд тэмдэгт мөрүүд нь хоорондоо огтлолцож эсвэл бүр нэг нэгнээ хучсан ч байж болно. Илүү дэлгэрэнгүй тайлбарлавал: $|w|$-аар $w$-ын уртыг тэмдэглэх бөгөөд $w$-ын тэмдэгтүүд нь $1$-ээс $|w|$ хүртэл дугаарлагдсан байна гэж үзье. Тэгвэл $w$ доторх $i$ байрлал бүрийн хувьд $w[l ... r]$ дэд тэмдэгт мөр нь $s_{1}, s_{2}, ..., s_{m}$ гэсэн цуглуулгын аль нэг элементтэй тэнцүү байх $l, r$ ($1 ≤ l ≤ i ≤ r ≤ |w|$) гэсэн хос индексүүд оршин байх ёстой юм.

Волл өгөгдсөн цуглуулгаар шүүгдсэн өгөгдсөн урттай DNA дарааллуудын тоог тооцоолохыг хүсэж байв. Гэхдээ тэрээр үүнийг хэрхэн хийхээ мэдэхгүй байгаа бөгөөд та түүнд туслах хэрэгтэй болжээ. Таны даалгавар бол ${s_{i}}$ цуглуулгаар шүүгдэх $n$ урт бүхий ялгаатай DNA дарааллуудын тоог олох юм.

Хариулт нь хэтэрхий том байж болох учраас $1000000009$ модулаар бодон хариултаа хэвлэнэ үү.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n ≤ 1000, 1 ≤ m ≤ 10$) өгөгдөх ба эдгээр нь харгалзан тэмдэгт мөрийн урт болон цуглуулга дотор байх дарааллуудын тоог илэрхийлнэ.

Дараагийн $m$ мөрөнд $s_{i}$ дарааллуудын цуглуулга өгөгдөх бөгөөд нэг дараалал нь нэг мөрөнд өгөгдөнө. $s_{i}$ бүр нь $10$-аас ихгүй урттай хоосон биш тэмдэгт байх бөгөөд бүх тэмдэгт мөрүүд нь "A", "C", "G", "T" гэсэн том үсгүүдээс тогтсон байна. Түүнчлэн цуглуулга нь ижил тэмдэгт мөрүүд агуулсан байж болно.

Гаралт

Цуглуулгаар шүүгдэх тэмдэгт мөрүүдийн (өөрөөр хэлбэл ялгаатай DNA дарааллууд) тоог $1000000009$ ($10^{9} + 9$) модулаар бодон хэвлэнэ үү.

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

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

Оролт
2 1
A
Гаралт
1
Оролт
6 2
CAT
TACT
Гаралт
2

Тэмдэглэл

Эхний жишээнд тэмдэгт мөр нь "A"-аар шүүгдэх ёстой байна. Тодруулбал ийм байх цор ганц тэмдэгт мөр байх бөгөөд энэ нь "AA" байх юм.

2-дахь жишээнд өгөгдсөн нөхцөлийг хангах яг 2 ширхэг ялгаатай тэмдэгт мөр оршин байна (доорх зургийг харна уу).

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