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”.

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 < K ≤ N) — 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).

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.