Высокоуровневые методы программирования рейтинговая Витте

Рейтинговая работа в виде расчетно-аналитического задания состоит из задания, по которому необходимо написать программу на языке Python. При этом оценивается не только получение конечного результата, но и качество кода программы и следование стилю, изложенному в учебном пособии. Решение задач расчетно-аналитического задания рассчитано на обретение навыков правильного применения языка Python в конкретных условиях, развитие профессиональных компетенций в целом. 

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть задана строка, в которой записано слово S, состоящее из N букв английского алфавита. Путем вычеркивания из этого слова некоторого набора символов, можно получить строку, которая будет палиндромом.

Требуется написать программу, с помощью которой можно определить, сколько существует способов вычеркивания из заданного слова некоторого (возможно пустого) набора символов, чтобы образованная таким образом строка была палиндромом. Способы, отличающиеся порядком вычеркивания символов, считаются одинаковыми.

В первой и единственной строке входного файла INPUT.TXT записано слово S, состоящее из N символов (1 ≤ N ≤ 30).

В выходной файл OUTPUT.TXT выведите найденное число способов.

№

INPUT.TXT

OUTPUT.TXT

1

AAA

7

2

BAOBAB

22