410529: GYM104035 4 Браслет

Варе подарили на День Рождения браслет, на котором по кругу записаны строчные английские буквы. Изучив внимательно браслет, Варя поняла, что на нём написано какое-то слово тарабарского языка состоящее из $$$N$$$ букв. Особенность слов тарабарского языка в том, что в них всегда от одной до восьми букв «a».

Подумав, Варя решила, что ей не нужен браслет, а нужна цепочка. И для этого ей нужно разрезать браслет ровно в одном месте, чтобы получившееся слово было палиндромом. Помогите Варе, подсчитайте, сколько есть способов разрезать браслет так, чтобы получилось слово-палиндром и определите позиции возможных разрезов — номера букв, после которых можно разрезать браслет (буквы в слове пронумерованы от $$$1$$$ до $$$N$$$).

Браслет из первого теста.

Для справки: палиндром — слово, одинаково читающееся в обоих направлениях, например «abba».

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 2 \cdot 10^6$$$) — длину слова на тарабарском языке.

Вторая строка содержит последовательность из $$$N$$$ строчных букв английского алфавита — слово на тарабарском языке.

В первой строке выведите целое число $$$K$$$ — количество способов разрезать браслет.

В следующих $$$K$$$ строках выведите позиции возможных разрезов. Выводить позиции можно в любом порядке.

В этой задаче 28 тестов, не считая тестов из условия. Каждый тест будет оцениваться независимо.

Решения, правильно работающие при $$$N \le 2000$$$, будут оцениваться в 36 баллов.

4
abba

2
2
4

5
arbat

0

В первом тесте разрезать браслет можно двумя способами. Можно сделать разрез между буквами $$$b$$$, тогда получится палиндром «baab», либо между буквами $$$a$$$, тогда получится палиндром «abba».

В втором тесте нельзя разрезать браслет так, чтобы получился палиндром.