We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Hyper Strings

Hyper Strings

Problem
Submissions
Leaderboard
Discussions
Editorial

String is called a Super String if and only if:

  • contains only letters ;
  • For any and , has lower ascii code than , where

Given a set of Super Strings , a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set . We can use each Super String as many times as we want.

Given set , you have to compute the number of Hyper Strings with length no greater than .

Input Format

The first line of input contains two integers, (the number of Super Strings in ) and . The next lines describe the Super Strings in set .

Constraints

and are not greater than .

Output Format

Output an integer which is the number of possible Hyper Strings that can be derived. Since it may not fit in bit integer, print the output module . (i.e. answer = answer % )

Sample Input

2 3  
a  
ab

Sample Output

7

Explanation

In the example all the Hyper Strings are : "" (empty string), "", "", "", "", "", and "".

Author

HackerRank

Difficulty

Advanced

Max Score

90

Submitted By

1765

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature