题目描述

记 $S(i,j)$ 为字符串 $S$ 的第 $i$ 个字母到第 $j$ 个字母组成的子串。

给出一个长度为 $n$ 由小写英文字母组成的字符串 $A$ 。

若字符串 $B$ 也由小写英文字母组成，长度为 $n$，且对于任意 $1 \leq i < j \leq n$ 有：若 $A(i,j)$ 是回文串，$B(i,j)$ 也是回文串；若 $A(i,j)$ 不是回文串，$B(i,j)$ 也不是回文串。那么我们称 $B$ 与 $A$ 是 ayq 相似的。

求有多少个字符串与 $A$ ayq 相似？输出答案对 $1000000007$ 取模的余数。

输入格式

输入 $1$ 行一个字符串 $A$。

输出格式

输出一行一个数表示所求答案

abcba

15600

数据范围与约定

对于 $100\%$ 的数据，$n \leq 1000000$