Формування потягу
Компанія, що займається перевезеннями по залізниці, отримала замовлення сформувати потяг, який складається з певного числа вагонів. Проблема у тому, що у компанії є вагони, випущені у різний час, так що кожен з вагонів може мати один з двох видів сцеплень на кожному кінці. У компанії також є один локомотив.
Сцеплення і для локомотиву, і для вагонів позначені літерою A або B. Повернути вагон чи локомотив протилежною стороною неможливо.
Задано інформацію про вагони і локомотив. Потрібно знайти кількість способів сформувати різні потяги заданої довжини з наявних видів вагонів. Додатковою вимогою є те, що тип сцеплень на кожному кінці сформованого потягу повинен відповідати типу сцеплень локомотива.
Потяги вважаються різними, якщо при їх порівнянні від одного кінця до іншого виявиться хоча б одна відмінність.
Приклад 1. Нехай у компанії є вагони AA, AA, AB, BA, BA і локомотив AB. У потязі повинно бути 4 вагони. Із заданих вагонів можна сформувати лише два різних потяги: BAAAABBA і BAABBAAA. Локомотив можна приєднати до потягу як ліворуч (використовуючи сцеплення B), так і праворуч (використовуючи сцеплення A).
Приклад 2. Нехай у компанії є лише по одному вагону кожного типа (AA, AB, BA, BB) і локомотив AA, а потяг повинен складатись з трьох вагонів. Існує три способи сформувати потяг: AAABBA, ABBAAA і ABBBBA.
Вхідні дані
У першому рядку через пропуск N - число вагонів, які знаходяться у розпорядженні компанії, і K - потрібна довжина потягу в вагонах. Другий рядок описує тип сцеплень локомотива. Наступні N рядків описують типи сцеплень вагонів. Описи задано як AB, AA, BB або BA.
1 ≤ K ≤ N ≤ 40.
Вихідні дані
У першому рядку виводиться слово "YES", якщо можна сформувати хоча б один потяг, або "NO" - у протилежному випадку.
Якщо потяг сформувати можливо, у другому рядку повинно бути вказана кількість способів це зробити.