Shuffle
ПрАнКА 2009
Time Limit: 0.4s, Memory Limit: 64MiB
Ели е голям фен на музиката! Тя успява да намери в нея много повече, отколкото нормалните тийнейджъри (а в house-а по принцип има доста да се търси докато се намери нещо хубаво).
Играейки си със своя iPod, момичето забеляза, че понякога се случва първите две букви от текущата песен да са същите, като последните две от предходната. Тя се замисли, че може повече от две песни да имат това свойство, като дефинира “cool последователност” по следния начин:
Един ден момичето се запита колко "cool" последователности от точно K песни има в нейната плейлиста. Две К-торки считаме за различни, ако едната съдържа поне една песен, която не се съдържа в другата. Вие решавате да й помогнете, като напишете програма, която намира това число.
Играейки си със своя iPod, момичето забеляза, че понякога се случва първите две букви от текущата песен да са същите, като последните две от предходната. Тя се замисли, че може повече от две песни да имат това свойство, като дефинира “cool последователност” по следния начин:
- Първите две букви от името на всяка от песните (освен първата) са последните две букви от името на предходната.
- Песните са наредени в същия ред (но не задължително последователни), в който са в нейния iPod.
Един ден момичето се запита колко "cool" последователности от точно K песни има в нейната плейлиста. Две К-торки считаме за различни, ако едната съдържа поне една песен, която не се съдържа в другата. Вие решавате да й помогнете, като напишете програма, която намира това число.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числата N и K – съответно броят песни в плейлистата на Ели, и колко песни трябва да съдържа "cool" последователността. На всеки от следващите N реда ще има по един стринг от малки латински букви Si – имената на песните, в реда, в който са в плейлистата на Ели. Гарантирано е, че няма да има две песни с еднакво име.
Изход
На стандартния изход изведете едно единствено цяло число – броят "cool" K-торки от плейлиста. Тъй като този брой може да стане голям, изведете единствено остатъка му по модул 1,000,000,007.
Ограничения
- 1 ≤ N ≤ 100,000
- 1 ≤ K ≤ 100
- 2 ≤ |Si| ≤ 20
Примерен Вход | Примерен Изход |
---|---|
7 2 danceforlife inandoutoflove feelthebeat atbextasy lovecomesagain whatelseisthere renegade | 3 |
Сред седемте дадени имена на песни търсим такива двойки, за които последните две букви на първата съвпада с първите две на втората. Има общо три такива двойки: (1, 3), (3, 4), и (6, 7).