C. Халаасны дэвтэр

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

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

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

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

Нэгэн өдөр Вася ээжийнхээ халаасны дэвтрийг олжээ. Дэвтэрт ээжийнх нь $n$ найзуудын нэрс ба нэр тус бүр яг $m$ үсэгнээс бүрдсэн байв. Нэрсийг бичигдсэн дарааллаар нь $1$-ээс $n$ хүртэл дугаарлая.

Ээж нь гэртээ байгаагүй тул Вася уг нэрсээр тоглохоор шийджээ. Тэр $i$, $j$, $k$ ($1≤iCBDAD" ба "AABRD" гэсэн нэрсийг аваад эхний $3$ үсгийг соливол үр дүнд нь "AABAD" ба "CBDRD" гэсэн нэрсийг гарган авна.

Дээр дурдсан үйлдлийг Вася хэдэн ч удаа гүйцэтгэж болно гэж үзвэл $1$ дугаартай нэрний оронд хэдэн ялгаатай нэрсийг үүсгэж болох вэ? Үйлдэл бүрт тэр $i$, $j$, $k$ тоонуудыг өмнөх үйлдлээс шалтгаалахгүй сонгох бөгөөд түүний сонголт түүний хүслээс бүрэн хамаарна. Хайж буй тоо маань маш том тоо байж болох тул $1000000007$ $(10^{9}+7)$-д хуваасан үлдэгдлийг олоорой.

Оролт

Оролтын эхний мөр нь нэрсийн тоо болон нэр тус бүрийн уртыг илэрхийлэх $n$ ба $m$ $(1≤n, m≤100)$ бүхэл тоог агуулна. Дараагийн $n$ мөрүүд нь нэрсийг агуулах ба нэр тус бүр нь яг $m$ ширхэг Латин том үсэгнээс бүрдэнэ.

Гаралт

Дээр өгүүлсэн үйл явцуудыг гүйцэтгэснээр халаасны дэвтэрний $1$ дугаартай байрлалд хэдэн ялгаатай нэр бичигдэхийг харуулах тоог $1000000007$ $(10^{9}+7)$-д хуваан үлдэгдлийг хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
2 3
AAB
BAA
Гаралт
4
Оролт
4 5
ABABA
BCGDG
AAAAA
YABSA
Гаралт
216

Тэмдэглэл

Эхний жишээнд, Вася $1$ дугаартай байрлалд дараах нэрсийг гаргаж авч болно. Үүнд: "AAB", "AAA", "BAA", "BAB".

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