Programmer's school

Forgot password?
[problems] [status] [courses] [info] [register]
Login:   Password:    

Sub-palindromes

(Time limit: 2 sec. Memory limit: 16 MB Difficulty: 59%)

A string is called a palindrome if it is read equally from left to right and from right to left. For example, the strings "abba" and "ata" are palindromes.

A substring of some string is a nonempty sequence of consecutive characters in the original string.

Find out how many substrings of a given string are palindromes.

Input

The only line of input contains a string consisting of characters with ASCII codes 33 to 127. The string length can be up to 105.

Output

Output one integer.

Samples

INPUT.TXTOUTPUT.TXT
1AAAA10
2ABRACADABRA13
3ABACABADABACABA32

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 C++ programming language
 Solution of olympiad tasks
 Regional competition
 Books by Fyodor Menshikov
 Training olympics
 Introduction
 Integer arithmetic
 Sorting algorithms
 Long arithmetic
 C++ Standard Template Library
 Dynamic programming
 Combinatorics
 Computational geometry
 String
 Data structures
 Graph theory - 1
 Graph theory - 2
 Simple tasks
 Algorithms on strings
 Polynomial hash
 A. Funktsiya Eylera
 B. Obratnyy element
 C. Hesh-funktsiya
 D. Vzlom hesh-funktsii
 E. Reklamnyy shchit
 F. Minimalnyy sdvig
 G. Slova
 H. Stroki - 3
 I. Podpalindromy
 J. Tsiklicheskie sdvigi

Krasnoyarsk regional Palace of pioneers, (c)2006 - 2022, E-mail: admin@acmp.ru