Problem Statement  
I love music and listen to it all the time. I have a huge amount of songs and often it's easy just to listen to them shuffled rather than to choose a song every time. But I listen to different genres of music and some of them are incompatible (for example, it's quite uncomfortable if some calm classic track is succeeded by a loud noisy song). So I wrote a program which performs the shuffled playback according to some rules.
Speaking formally, I have defined several genres and ascribed each of the songs to one specific genre. I have also defined which genres are compatible, i.e. can be listened to in immediate succession and which are not. The jth character of the ith element of String[] transitions is 'Y' if a song of genre i can be succeeded by a song of genre j, and is 'N' otherwise. My program works in the following way: it randomly chooses the first song to play. When the track finishes, the next song is chosen from the set of all songs of compatible genre(s), and so on. The same song may be played several times and it might even happen that the same song is played several times in a row. You're given String[] songs. Concatenate the elements of songs to obtain a list of the songs. The list will be formatted as a commaseparated list of spaceseparated pairs of integers, the first of them denoting the genre of the song and the second one denoting its length in minutes. Count the number of different song sequences which might be played using my program and are between minLength and maxLength (both inclusive) minutes long, and return it modulo 600,921,647.  
Definition  
 
Constraints  
  transitions will contain exactly n elements, where n is between 1 and 9, inclusive.  
  Each element of transitions will contain exactly n characters.  
  transitions will contain only 'N' and 'Y' characters.  
  For each i between 0 and n1, the ith character of the ith element of transitions will be 'Y'.  
  songs will contain between 1 and 50 elements, inclusive.  
  Each element of songs will contain between 1 and 50 characters, inclusive.  
  The concatenation of the elements of songs will be a commaseparated list of spaceseparated pairs of integers.  
  The first integer of each pair will be between 0 and n1, inclusive, with no extra leading zeroes.  
  The second integer of each pair will be between 1 and 9, inclusive, with no leading zeroes.  
  minLength will be between 1 and 1,000,000,000, inclusive.  
  maxLength will be between minLength and 1,000,000,000, inclusive.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
