Masala #LPVZGVPTCH
Tartiblash 2
Davlatbek o'z shogirdlarini yana bir marta tartiblashga qaror qildi. Bu safar u o'z ro'yxati estetik jihatdan yoqimli bo'lishini xohlaydi, shuning uchun u o'xshash ismlar (bir xil harf yoki harflar ketma-ketligi bilan boshlangan) ro'yxatda bir-biriga yaqin bo'lishi kerak, deb qaror qildi. Shuning uchun u quyidagi qoidani ishlab chiqdi:
Roʻyxatdagi bir xil harflar ketma-ketligi bilan boshlanadigan har ikki ism uchun ularning orasidagi barcha ismlar ham shu harflar ketma-ketligidan boshlanishi kerak.
Misol uchun, SHOHRUH va SHOHJAHON ismlarini ko'rib chiqing Ularning ikkalasi ham SHOH ketma-ketligi bilan boshlanadi, shuning uchun bir xil ketma-ketlik bilan boshlanadigan ismlar (masalan, SHOHSANAM va SHOHBOZ) orasida paydo bo'lishi mumkin (lekin SHAXZODA emas).
E'tibor bering, leksikografik tartiblangan tartib har doim bu qoidaga javob beradi, lekin bu yagona to'g'ri tartib emas. Sizning vazifangiz qancha turli xil tartib qoidaga mos kelishini aniqlashdir, ya'ni Davlatbek o'zining reyting ro'yxati uchun nechta variantga ega.
Kirishning birinchi qatorida N musbat butun son, ismlar soni mavjud.
Quyidagi N satrlarning har biri bitta ismdan iborat: 1 dan 3000 gacha inglizcha bosh harflar ketma-ketligi. Ismlar turlicha.
\(3 ≤ N ≤ 3000\)
Javobni \(10^9+7\) ga bo'lgandagi qoldig'ini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 DILSHOD ASILBEK DILYOR |
4 |
| 2 |
5 MARDON MARJONA MADINA MAHMUDA MAHMUD |
24 |
1-test uchun mavjud tartiblar:
[DILSHOD, DILYOR, ASILBEK]
[DILYOR, DILSHOD, ASILBEK]
[ASILBEK, DILYOR, DILSHOD]
[ASILBEK, DILSHOD, DILYOR]
Telegram kanalimizga obuna bo'ling