> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-1/g-palindromic-naming.md).

# G: Palindromic Naming

https\://open.kattis.com/problems/palindromic

* Firstly, notice that the problem is essentially asking for the number of subsequences of the original string that are palindromes. As there are exponentially many subsequences, generating all possible subsequences and checking if it is a palindrome is too slow!
* You can use **dynamic programming** to solve this problem :)
* Let $$dp\[i]\[j]$$ **denote the number of palindromic subsequences of the substring** $$s\_is\_{i+1}...s\_j$$**.**

{% hint style="warning" %}
Note that the empty string is not considered a palindrome.
{% endhint %}

* Firstly, $$dp\[i]\[i]=1$$ for all positions $$i$$ as any string of length $$1$$ is a palindrome. Further, $$dp\[i]\[i+1]=3$$ if $$s\_i=s\_{i+1}$$ as $$s\_i$$, $$s\_{i+1}$$, and $$s\_is\_{i+1}$$ are all palindromes. Otherwise, $$dp\[i]\[i+1]=2$$ as only $$s\_i$$ and $$s\_{i+1}$$are palindromes.
* We **iterate in increasing order of widths** `w`. In other words, we first considering all palindromic subsequences at most 2 characters apart, then at most 3 characters apart and so on.
* Now, our transitions:
  1. If $$s\_i \neq s\_j$$, we cannot create any new palindromes using the characters at positions $$i$$ and $$j$$. Thus, by[ inclusion-exclusion](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle), $$dp\[i]\[j]=dp\[i]\[j-1]+dp\[i+1]\[j]-dp\[i+1]\[j-1]$$.
  2. If , $$s\_i = s\_j$$​, for every palindrome in $$s\_{i+1}...s\_{j-1}$$, we can add $$s\_i$$and $$s\_j$$to create a new palindrome $$s\_is\_{i+1}...s\_{j-1}s\_j$$​. Furthermore, $$s\_is\_j$$​is also a palindrome. So, we have $$dp\[i+1]\[j-1]+1$$ new palindromes in addition to the ones we already had. So, in this case, $$dp\[i]\[j]=dp\[i]\[j-1]+dp\[i+1]\[j]+1$$.
* The required answer is $$dp\[1]\[n]$$.

{% hint style="warning" %}
Remember to perform all calculations modulo 1 000 000 007. 
{% endhint %}