E. Женоме-ыг тайлж унших

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

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

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

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

Саяхан Ангараг гариг уруу явах маш нууц даалгаврыг биелүүлжээ. Үр дүнд нь эрдэмтэд Ангарагийн хүний DNA-ын тухай хэсэг мэдээлэлтэй болжээ. Одоо бид ямар ч Ангарагийн хүний DNA нь хамгийн ихдээ $1$-ээс $m$ хүртэл дугаарлагдсан $m$ ширхэг ялгаатай нуклеотиде-ууд агуулна гэдгийг мэдэж байгаа. Ангарагийн хүний DNA-ын онцгой шинж чанарууд нь уг DNA-ын холбоос дотор дараалан орох зарим хос нуклеотиде-уудын талаар сануулав. Жишээлбэл, хэрэв нуклеотиде 1 болон нуклеотиде 2 нь уг Ангарагийн хүний DNA-ын холбоос дотор дараалан орж чадахгүй бол нуклеотиде-уудын холбоос [1, 2] нь Ангарагийн хүний DNA-ын боломжит холбоос биш байх юм. Гэхдээ нуклеотиде-уудын холбоос [2, 1] нь боломжит холбоос байж болно (хэрэв ямар нэгэн харгалзах хязгаарлалт байхгүй бол). DNA холбоос дотор дараалан орж чадахгүй хос нуклеотиде-уудын тоо нь $k$ байна.

Генийн судалгааны төв нь Ангарагын хүний DNA-ын $n$ урттай зөв холбоосуудын тооны талаар мэдээлэл авахыг хүсжээ. Таны даалгавар бол уг утгыг тооцоолох программ бичих юм.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 3 бүхэл тоо $n, m, k$ ($1 ≤ n ≤ 10^{15}$, $1 ≤ m ≤ 52$, $0 ≤ k ≤ m^{2}$) өгөгдөнө.

Дараагийн $k$ мөрийн мөр болгонд хоорондоо зайгүй 2 тэмдэгт өгөгдөх ба эдгээр нь хориглогдсон нуклеотиде хосыг илэрхийлнэ. Эхний тэмдэгт нь хориглогдсон хосын эхний нуклеотиде-ыг 2-дахь тэмдэгт нь хориглогдсон хосын 2-дахь нуклеотиде-ыг илэрхийлнэ.

1-ээс 26 хүртэл дугаарлагдсан нуклеотиде-ууд нь Англи цагаан толгойн "$a$"-аас "$z$" хүртэлх үсгүүдээр илэрхийлэгдэнэ (1 нь "$a$", 2 нь "$b$", $...$, 26 нь "$z$"). 27-оос 52 хүртэл дугаарлагдсан нуклеотиде-ууд нь Англи цагаан толгойн "$A$"-аас "$Z$" хүртэлх үсгүүдээр илэрхийлэгдэнэ (27 нь "$A$", 28 нь "$B$", $...$, 52 нь "$Z$").

Оролтод хориглогдсон хос болгон нь хамгийн ихдээ нэг удаа өгөгдөнө. Бүх хориглогдсон хосууд доторх нуклеотиде-ын дугаарууд нь $m$-ээс ихгүй байна. Нуклеотиде хосуудын дараалал чухал болохыг анхаарна уу.

С++ дээр 64-битийн бүхэл тоонуудыг унших болох бичихдээ %lld тодорхойлогчийг битгий ашиглана уу. cin, cout streams эсвэл %I64d тодорхойлогч ашиглахыг илүүд үзнэ үү.

Гаралт

Хайж буй тоог $1000000007$ $(10^{9} + 7)$ модулаар бодон хэвлэнэ үү.

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

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

Оролт
3 3 2
ab
ba
Гаралт
17
Оролт
3 3 0
Гаралт
27
Оролт
2 1 1
aa
Гаралт
0

Тэмдэглэл

2-дахь жишээнд бүх боломжит 3 нуклеотиде-тай DNA-ын холбоосууд нь зөвшөөрөгдсөн байна. Нуклеотиде болгон нь эдгээр 3 утгын нэгийн авах ба иймд нийт 27 ширхэг ялгаатай 3 нуклеотиде-тай DNA-ын холбоосууд байна.

3-дахь жишээнд бид ямар ч 2 нуклеотиде-тай DNA-ын холбоос бүтээж чадахгүй учир нь ганц байгаа боломжит нуклеотиде нь $a$ нь 2 удаа дараалан орж болохгүй юм.

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