“One chord is fine. Two chords are pushing it. Three chords and you’re into jazz.”
-Lou Reed
Do you know what is guitar chord? In music, a guitar chord is a set of notes played simultaneously or sequentially on a guitar. You also need to know about note to understand this definition. In music note is a single tone or sound in a specific frequency. In guitar string we can make a lot of sounds depending on frets and thickness of the guitar strings. Every sounds of different frequency are named differently. Let’s see all of the available notes-
A A# B C C# D D# E F F# G G#
Consecutive 12 notes are known as octave. As we know there are a lot of positions in a guitar which can produce sounds, so these 12 notes repeatedly take place, with the same sequence in the guitar strings as well as any other musical instruments. Follow this fret-board of a guitar for better understanding-
In the given image, the guitar is tuned as E B G D A E, that means, 1st string is started from E, second string from B, third string from G and so on. Depending on the tune of the guitar, other notes took place with the relation of tuned note. For example, the 1st string is tuned in E, so according to the sequence of notes, the first fret is F, second fret is F# and so on. But if I change it’s tune to G# then the first fret will be A, second fret will be A# and so on.
To play a chord in this guitar, select and touch required notes using fingers of one hand then stroke all of the strings toward up and down using another hand. If you leave a string untouched, the open note (tuned note) will be played. But keep in mind that you can play same note in different string but you cannot play multiple notes in a same string at a time.
There are several types of guitar chord like Major, Minor, 5th, 7th, Major 7th, Minor 7th, Suspended*, Diminished*, Augmented*, Added* etc. But in this problem we are going to create Major, Minor and 7th chords only.
Chords will be denoted as a Note followed by M for Major, m for minor and 7 for 7th chord separated by space. For example C M, G m, F# 7 etc.
To build a chord you have to know that, when you are asked to create a chord of specific note, consider the chord note as the first note of the sequence. Then you have to select and play set of different notes for different chords. Suppose you are asked to create a chord of note C, then the sequence will be-
C C# D D# E F F# G G# A A# B
In this sequence for Major (M) chord you have to play 1st, 5th & 8th note, for Minor (m), 1st, 4th & 8th note and for 7th (7), 1st 5th, 8th & 11th note.
Example:
CM: C E G, Cm: C D# G, C7: C E G A#
F#M: F# A# C#, F#m: F# A C# F#7: F# A# C# E
Before you start making chords, I would like to inform you that, in the real world a guitar contains 4 to 27 or more strings with 19 to 27 or more frets. To create a chord, a guitarist chooses notes such a way that distance of any pair of two fingers (which are used to hold the notes of the frets) will not exceed M, but it’s possible to touch multiple notes in one fret in different strings.
There are several ways of creating a single chord in a guitar. Here are few ways of C Major chord in the first 4 frets of a guitar, which contains 6 strings and tuned as E B G D A E-
If you can create chords correctly, I think you can count ways of making a specific chord in any guitar.
Input
There will be at most 20 test cases in the input file. First line of an input set will contain 3 integers S (1<S<100), F (1<F<100), M (1<M<10) where S denotes number of strings, F denotes number of frets and M denotes the maximum distance of any pair of two fingers. Next line will contain the tune of the guitar containing S notes separated by space. Next line will contain an integer C (1<C<50) followed by C lines containing name of a chord in each line.
Output
For each C line of input you have to output the count of possible ways of creating that chord in the given guitar. As the result can be bigger, so mod the result by 1000000027.
Sample
| Input | Output |
|---|---|
6 21 3 E B G D A E 3 C M C m C 7 4 12 6 A E C G 3 G# M E m F 7 | 33 7 71 18 28 15 |
