CF832E Vasya and Shifts

Vasya has a set of $ 4n $ strings of equal length, consisting of lowercase English letters "a", "b", "c", "d" and "e". Moreover, the set is split into $ n $ groups of $ 4 $ equal strings each. Vasya also has one special string $ a $ of the same length, consisting of letters "a" only. Vasya wants to obtain from string $ a $ some fixed string $ b $ , in order to do this, he can use the strings from his set in any order. When he uses some string $ x $ , each of the letters in string $ a $ replaces with the next letter in alphabet as many times as the alphabet position, counting from zero, of the corresponding letter in string $ x $ . Within this process the next letter in alphabet after "e" is "a". For example, if some letter in $ a $ equals "b", and the letter on the same position in $ x $ equals "c", then the letter in $ a $ becomes equal "d", because "c" is the second alphabet letter, counting from zero. If some letter in $ a $ equals "e", and on the same position in $ x $ is "d", then the letter in $ a $ becomes "c". For example, if the string $ a $ equals "abcde", and string $ x $ equals "baddc", then $ a $ becomes "bbabb". A used string disappears, but Vasya can use equal strings several times. Vasya wants to know for $ q $ given strings $ b $ , how many ways there are to obtain from the string $ a $ string $ b $ using the given set of $ 4n $ strings? Two ways are different if the number of strings used from some group of $ 4 $ strings is different. Help Vasya compute the answers for these questions modulo $ 10^{9}+7 $ .

The first line contains two integers $ n $ and $ m $ ( $ 1

For each string Vasya is interested in print the number of ways to obtain it from string $ a $ , modulo $ 10^{9}+7 $ .

In the first example, we have $ 4 $ strings "b". Then we have the only way for each string $ b $ : select $ 0 $ strings "b" to get "a" and select $ 4 $ strings "b" to get "e", respectively. So, we have $ 1 $ way for each request. In the second example, note that the choice of the string "aaaa" does not change anything, that is we can choose any amount of it (from $ 0 $ to $ 4 $ , it's $ 5 $ different ways) and we have to select the line "bbbb" $ 2 $ times, since other variants do not fit. We get that we have $ 5 $ ways for the request.