Train Formation
A railway transportation company has received an order to assemble a train consisting of a specific number of carriages. The challenge is that these carriages were manufactured at different times, so each one may have one of two types of couplings on each end. Additionally, the company has one locomotive.
Both the locomotive and the carriages have couplings labeled as either A or B. It is important to note that neither the carriages nor the locomotive can be turned around to use the opposite side.
You are provided with information about the carriages and the locomotive. Your task is to determine the number of ways to assemble different trains of a specified length using the available carriages. A key requirement is that the couplings at each end of the assembled train must match those of the locomotive.
Trains are considered different if, when compared from one end to the other, there is at least one difference.
Example 1. Suppose the company has carriages AA, AA, AB, BA, BA, and a locomotive AB. The train must consist of 4 carriages. From the available carriages, only two distinct trains can be formed: BAAAABBA and BAABBAAA. The locomotive can be attached to the train either on the left (using coupling B) or on the right (using coupling A).
Example 2. Suppose the company has one carriage of each type (AA, AB, BA, BB) and a locomotive AA, and the train must consist of three carriages. There are three ways to form the train: AAABBA, ABBAAA, and ABBBBA.
Input
The first line contains N - the number of carriages available to the company, and K - the required train length in carriages, separated by a space. The second line describes the type of couplings of the locomotive. The next N lines describe the types of couplings of the carriages. The descriptions are given as AB, AA, BB, or BA.
1 ≤ K ≤ N ≤ 40.
Output
The first line should output the word "YES" if at least one train can be formed, or "NO" if it cannot.
If forming a train is possible, the second line should indicate the number of ways to do so.