Рассмотрим одну интересную игру со словами. В этой игре требуется из одного слова получить другое посредством специальных операций.
Пусть у нас есть слово w, разделим это слово на две непустые части x и y так, что w = xy. Операцией split, назовем преобразование слова w = xy в слово u = yx. Например, слово «wordcut» посредством одной операции split можно преобразовать в слово «cutword».
Вам даны два слова start и end. Посчитайте сколькими способами можно получить из слова start слово end, применив к слову start последовательно ровно k операций split.
Два способа считаются различными, если различаются последовательности примененных операций. Две последовательности операций различны, если существует такой номер i (1 ≤ i ≤ k), что в i-ой операции первой последовательности слово делится на части x и y, в i-ой операции второй последовательности слово делится на части a и b, и при этом x ≠ a.