• 46

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

We say a tuple of three strings (P, Q, R) is a palindromic decomposition of string S if P+Q+R=S and all of P, Q and R are palindrome. Note that P, Q and R can be the empty string ε.

Given string S, calculate the number of the palindromic decompositions of S.

For example, if you are given abab, you should answer 6 because (ε, a, bab), (ε, aba, b), (a, ε, bab), (a, bab, ε), (aba, ε, b) and (aba, b, ε) are the palindromic decompositions of abab.
Input
A string S.
Output
The number of palindromic decompositions of S.
Constraints
1 ≤ length of S ≤ 4000.
S is consisting of lowercase English letters.
Example
Input
```abab
```
Output
```6
```

A higher resolution is required to access the IDE   Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
Online Participants