小 虽然是一名理科生，但他常常称自己是一名真正的文科生。不知为何，他对于背诵总有一种莫名其妙的热爱，这也促使他走向了以记忆量大而闻名的生物竞赛。然而，他很快发现这并不能满足他热爱背诵的心，但是作为一名强大的 OIER，他找到了这么一个方法——背诵基因序列。然而这实在是太困难了，小 感觉有些招架不住。
不过他发现，如果他能事先知道这个序列里有多少对互不相交的回文串，他或许可以找到记忆的妙法。为了进一步验证这个想法，小 决定选取一个由小写字母构成的字符串 来实验。由于互不相关的回文串实在过多，他很快就数晕了。不过他相信，在你的面前这个问题不过是小菜一碟。
-
对于字符串 ，设其长度为 ，那么下文用 表示 中第 个字符（）。
-
表示 的一个子串，，比如当 为 时， 就是 ， 是 。
-
当一个串被称为一个回文串当且仅当将这个串反写后与原串相同，如 。
-
考虑一个四元组 ，当 和 均为回文串时，且满足 时，我们称 和 为一对互不相交的回文串。本题所求也即为这种四元组的个数。两个四元组相同当且仅当对应的 都相同。
