Remote Training on Programming

Группа болельщиков ФК «Чукотка» составила фанатскую кричалку в поддержку любимой команды. Кричалка удалась на славу! Но вскоре выявился один ее серьезный недостаток — она оказалась слишком длинной, и мало кому удалось запомнить ее наизусть.

Тогда кричалку решили переделать так, чтобы ее слова были подчинены некоторой логической последовательности. Таким образом даже те, кто не помнил слов наизусть, всегда могли восстановить текст кричалки.

Кричалку было решено составить по следующей схеме. В основу брались две ключевые фразы — A и B. Каждая фраза могла состоять из нескольких слов. После этого строилась такая последовательность кричалок: T₀ = A, T₁ = B, T₂ = AB, T₃ = BAB, ... , T_n = T_{n - 2}T_{n - 1}

Таким образом, кричалка T_i состояла из последовательного исполнения кричалок T_{i - 2} и T_{i - 1}.

Составленная таким образом кричалка пользовалась большим успехом. Особой гордостью болельщиков ФК «Чукотка» был тот факт, что длину кричалки можно было легко варьировать на протяжении матча — в зависимости от ситуации на поле.

Теперь болельщики, самым рьяным из которых является губернатор Абрам Романович, по совместительству курирующий команду своего округа, хотят исполнять кричалку так, чтобы заданное слово S встречалось в ней некоторое фиксированное число раз K.

Вам, как одному из лидеров фанатского движения, требуется, зная начальные ключевые фразы A и B, слово S, встречающееся в одной или обеих из них, а также номер K, определить число N — наименьший номер кричалки T_N, в которой слово S встречается ровно K раз.