start и goal одинаковой длины n. За один ход от текущей строки отрезают хвост длиной от 1 до n − 1 и переставляют его в начало. Например, из abcd, перенеся хвост cd, получаем cdab.
Посчитайте, сколькими способами можно сделать ровно moves ходов так, чтобы из start получилась goal. Способы различаются, если хотя бы на одном ходу выбрана другая длина хвоста. Ответ может быть огромным, поэтому верните его по модулю 10⁹ + 7.start='abc', goal='abc', moves=2 → 2
Ходом можно перенести в начало хвост длины 1 или 2. Чтобы за два хода вернуться к abc, подходят пары «1, затем 2» (abc → cab → abc) и «2, затем 1» (abc → bca → abc).
start='abab', goal='abab', moves=1 → 1
Из трёх возможных хвостов только перенос ab оставляет строку прежней.
start.length ≤ 5·10⁵goal.length == start.lengthmoves ≤ 10¹⁵start и goal состоят только из строчных латинских буквstart='abc', goal='abc', moves=2
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 61 тест на сервере, включая скрытые.