PROGRAMING PROBLEMS

N хэсэгт хуваасан үгс өгчээ. Эдгээр үгсийн i дүгээр хэсэг дахь үгс яг i үсэг орсон байна. Мөн хэсэг бүрд яг K үг бий. Тэгвэл дараах шаардлагыг хангаж байх N тооны үгсийг хэчнээн янзаар сонгон авч болох вэ? 

• Сонгон авсан үгс ялгаатай урттай байх ёстой.

• Тухайн үг нь түүнээс урт үгийн тасралтгүй дараалал байх ёстой.

Тооцооллын үр дүнг 10⁹ +7 хувааж үлдэгдлийг үр дүн болгон авна.

Оролт:

Эхний мөрд N (1 ≤ N ≤ 50) ба K (1 ≤ K ≤ 1 500) тоо байна. Дараагийн N мөр нь бүрд K тооны ялгаатай үгс байна. i дүгээр мөрд буй үгс нь яг i ширхэг Англи жижиг үсгээс бүтсэн байна.

Гаралт:

Бодлогын шийд болох ганц ширхэг бүхэл тоог агуулсан ганц мөртэй байна.

Үнэлгээ:

Subtask Score Constraints 1 22 N = 5 and K = 10 2 33 N = 50 and K = 100 3 55 No additional constraints.

Тестийн 22 хүртэлх онооны тестэд N=5 ба K=10

Тестийн 33 хүртэлх онооны тестэд N=50 ба K=100

Харин 55 хүртэлх онооны тестэд хязгаарлалт байхгүй.

Жишээ:

Эхний жишээний тайлбар: Бодлогын шаардлагад нийцэхээр (a, ab, abc), (a, ab, abd), (b, ab, abc), (b, ab, abd) ба (b, bd, abd) гэсэн 5 өөр үгсийг сонгон авч болно.