`#include <bits/stdc++.h> `

`using`

`namespace`

`std; `

`#define N 100 `

` `

`void`

`pre_process(`

`bool`

`dp[N][N], string s) `

`{ `

` `

` `

` `

`int`

`n = s.size(); `

` `

` `

` `

` `

`for`

`(`

`int`

`i = 0; i < n; i++) { `

` `

`for`

`(`

`int`

`j = 0; j < n; j++) `

` `

`dp[i][j] = `

`false`

`; `

` `

`} `

` `

` `

` `

`for`

`(`

`int`

`j = 1; j <= n; j++) { `

` `

` `

` `

` `

`for`

`(`

`int`

`i = 0; i <= n - j; i++) { `

` `

` `

` `

`if`

`(j <= 2) { `

` `

` `

` `

`if`

`(s[i] == s[i + j - 1]) `

` `

`dp[i][i + j - 1] = `

`true`

`; `

` `

`} `

` `

` `

` `

`else`

`if`

`(s[i] == s[i + j - 1]) `

` `

`dp[i][i + j - 1] = dp[i + 1][i + j - 2]; `

` `

`} `

` `

`} `

`} `

` `

`int`

`countPairs(string s) `

`{ `

` `

` `

` `

`bool`

`dp[N][N]; `

` `

`pre_process(dp, s); `

` `

`int`

`n = s.length(); `

` `

` `

` `

`int`

`left[n]; `

` `

`memset`

`(left, 0, `

`sizeof`

`left); `

` `

` `

` `

`int`

`right[n]; `

` `

`memset`

`(right, 0, `

`sizeof`

`right); `

` `

` `

` `

`left[0] = 1; `

` `

` `

` `

` `

`for`

`(`

`int`

`i = 1; i < n; i++) { `

` `

` `

`for`

`(`

`int`

`j = 0; j <= i; j++) { `

` `

` `

`if`

`(dp[j][i] == 1) `

` `

`left[i]++; `

` `

`} `

` `

`} `

` `

` `

` `

`right[n - 1] = 1; `

` `

` `

` `

` `

`for`

`(`

`int`

`i = n - 2; i >= 0; i--) { `

` `

` `

`right[i] = right[i + 1]; `

` `

` `

`for`

`(`

`int`

`j = n - 1; j >= i; j--) { `

` `

` `

`if`

`(dp[i][j] == 1) `

` `

`right[i]++; `

` `

`} `

` `

`} `

` `

` `

`int`

`ans = 0; `

` `

` `

` `

`for`

`(`

`int`

`i = 0; i < n - 1; i++) `

` `

`ans += left[i] * right[i + 1]; `

` `

` `

`return`

`ans; `

`} `

` `

`int`

`main() `

`{ `

` `

`string s = `

`"abacaba"`

`; `

` `

`cout << countPairs(s); `

` `

` `

`return`

`0; `

`} `