#P3103. Palindromic Equivalence

    ID: 2225 传统题 1000ms 512MiB 尝试: 183 已通过: 71 难度: 9 上传者: 标签>CF2800省选/NOI-Manacher奇偶回文统一普通并查集顶点着色完美消除序列乘法原理时间戳避免清空数组

Palindromic Equivalence

题目描述

给出一个由小写字母组成的字符串 ss,问有多少由小写字母构成的字条串 s′s' ,满足:

  1. ∣s∣′=∣s∣ |s|'=|s|;
  2. s′[l…r]s'[l\dots r] 是回文串,当且仅当 s[l…r]s[l\dots r] 是回文串。

输入格式

一个字符串 ss。

输出格式

输出答案 mod  109+7\mod 10^9+7。

abba
650

样例说明

Only words of the form xyyx are palindromically equivalent to abba, where x and y are distinct letters. The English alphabet contains 2626 letters, consequently there are 26×25=65026\times25=650 such words in total.

数据规模与约定

对于 100%100\% 的数据,ss 长度 ≤106\le 10^6。