Вам дана строка \(s\) над бинарным алфавитом.
Посчитайте количество различных циклических строк длины \(n\) над бинарным алфавитом, которые содержат \(s\) как подстроку.
Циклическая строка \(t\) содержит \(s\) как подстроку если существует какой-то циклический сдвиг строки \(t\), такой что \(s\) является подстрокой этого циклического сдвига строки \(t\).
Например, циклическая строка «000111» содержит подстроки «001», «01110» и «10», но не содержит «0110» и «10110».
Две циклические строки называются различными, если они отличаются как строки. Например, две различные строки, которые отличаются друг от друга циклическим сдвигом, являются различными циклическими строками.
Примечание
В первом примере есть три циклических строки, которые содержат "0" — "00", "01" и "10".
Во втором примере есть только две такие строки — "1010", "0101".