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

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

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

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

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

№

INPUT.TXT

OUTPUT.TXT

1

AAA

7

2

BAOBAB

22