ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Quarterfinal, Rybinsk, October 16 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Train

Time limit: 1.0 second
Memory limit: 4 MB
Train Ltd., a company that is in for railroad transportation received an order to form a train having a certain number of carriages. The problem is that Train Ltd. has carriages built in different years, therefore each of the carriages may have one of the two kinds of coupling at each side. The company also has one locomotive at its disposal.
The coupling systems for both the locomotive and the carriages are labeled as “A” or “B”. It is impossible to turn either the locomotive or a carriage in the opposite direction.
You are given information about the carriages and the locomotive. Your task is to determine the number of ways to form different trains using the given carriages. The additional requirement is that the coupling systems at each of the ends of the train must correspond to those of the locomotive.
The trains are considered different if there is at least one mismatch when they are compared from one end to another.
Example 1. Let the company possess the following carriages: “AA”, “AA”, “AB”, “BA”, “BA” and the locomotive “AB”. The train must have four carriages. Then it is possible to form only two different trains having these carriages: “BAAAABBA” and “BAABBAAA”. It is possible to connect the locomotive at the left end of this train (using coupling “B”) or at the right one (using coupling “A”).
Example 2. Let the company now have only one carriage of each type: “AA”, “AB”, “BA”, “BB”, and the locomotive is “AA”. The train must have three carriages now. There are three ways to form a train: “AAABBA”, “ABBAAA” and “ABBBBA”.

Input

The first line of the input contains two integers separated with white-space character: N (0 < N ≤ 40) — the number of carriages the company has at its disposal, and K (0 < KN) — the required length of the train (measured in carriages). The following N + 1 lines describe the coupling systems for the locomotive (line 2) and the carriages. These descriptions are given as “AB”, “AA”, “BB” or “BA” (without quotes).

Output

Write the word “YES” if it is possible to form one (or more) trains according to the given parameters, or “NO” otherwise. If it is possible to form a train then write the number of different ways of doing so to the second line.

Samples

inputoutput
4 4
AB
AA
AB
BA
BA
YES
2
4 4
BA
AA
AB
BA
BA
NO
Problem Author: © Sergey G. Volchenkov, 2003(volchenkov@yandex.ru); Vladimir N. Pinaev, 2003(vpinaev@mail.ru; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (mkopachev@krista.ru).
Problem Source: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003
To submit the solution for this problem go to the Problem set: 1276. Train