time limit per test: 0.25 sec. memory limit per test: 65536 KB
input: standard output: standard
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.
3 15 Hedgehog
Anton Golubev, Petrazavodsk SU
Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
August 26, 2005
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov