Программа: слова без одинаковых соседних букв

Из букв заданного алфавита составляются слова длины L (словом считается любая последовательность букв алфавита, буквы могут повторяться). Слово называется допустимым, если в нём: — выделенная буква C встречается ровно K раз; — никакие две соседние буквы не совпадают. Напишите программу, которая определяет количество допустимых слов и выводит первое из них в алфавитном (лексикографическом) порядке латинских букв. Входные данные: в первой строке — алфавит: от 2 до 6 различных заглавных латинских букв без пробелов (буквы не обязательно упорядочены); во второй строке — числа L и K через пробел (1 ≤ L ≤ 8, 0 ≤ K ≤ L); в третьей строке — буква C (она входит в алфавит). Гарантируется, что (количество букв алфавита)^L ≤ 100 000. Выходные данные: в первой строке — количество допустимых слов, во второй — первое допустимое слово в алфавитном порядке. Если допустимых слов нет, во второй строке выведите символ - (минус). Пример. Входные данные:

KTA
4 1
A

Выходные данные:

12
AKTK