295. Identifier Duplicated!
time limit per test: 0.25
memory limit per test: 65536
On the first of April Qc cracked one of the most popular Karelian chats. Before his unlawful action only Latin letters, digits and space characters could be used in nicknames. But now users can use digits, spaces and both Latin and Russian letters. Certainly, this change brings the possibility of multing. Multing means that the new user is able to register under a nickname that looks like the existing one. For example, if there exists the user with the nickname "Hedgehog", the new user can get a nickname by replacing the first Latin letter "H" with Russian "H". Moreover, it is possible to change several letters at once; add or remove spaces.
Qc wants to know how many different mults exist for the given nickname.
Let us determine the set of Latin letters that are readable as Russian ones:
A, B, C, E, H, K, M, O, P, T, X, a, c, e, o, p, x, y.
Two words are mults of each other if one can be transformed to another by replacing one or several of its Latin letters with its Russian analog or vice versa, changing the number of spaces between words, adding or removing leading and trailing spaces. Note, that it is not allowed to delete all spaces between a pair of words, or add new spaces in the middle of the word.
The first line of the input file contains two numbers q and c (1 <= q <= c <= 63) separated by one space. The length of registered nickname must be not less than q letters and no more than c. The second line contains nickname consisting only of Latin letters, digits and space characters.
Output the number of mults for the given nickname under the given restrictions.
|Author:||Anton Golubev, Petrazavodsk SU
|Resource:||Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
|Date:||August 26, 2005
|Server time: 2018-06-20 21:04:41||Online Contester Team © 2002 - 2016. All rights reserved.|