测试数据来自 system/1890

描述

小岛: doc快来看, 这两个id长得好像呀! 一个是 sevenk 一个是 atutcf.
doc : 啊? 为何说它们像呢?
小岛: 因为呀: 首先它们长度相同, 其次呢, 第一个里面的某一连续子串是 回文 当且仅当 第二个里面对应为之的连续子串也是回文.
doc : 啊! 是的呀, 那么 seter 和 ahohr 也很像呢!
小岛: 对呀, 不过 seter 和 setes 就不像了, 因为第二个本身是回文的, 但是第一个却不是.
doc : 包括 seter 与 sater 也不像了.

wish: 话说, 如果我给你们一个长度为 n 的字符串, 究竟有多少与它相似的字符串呢?
doc : 我们简化一下问题吧, 假设字符串中只允许使用小写字母 a 到 z 吧.

格式

输入格式

输入只有一行, 是由小写字母组成的字符串.

输出格式

输出只有一行, 给出与给定字符串相似的字符串总数, 只需要输出总数关于 1000000007 取模后的数字.

样例1

样例输入1

abba

样例输出1

650

限制

对于 24% 的数据, 字符串长度 <= 10
对于 56% 的数据, 字符串长度 <= 1000
对于 100%的数据, 字符串长度 <= 1000000

提示

对于样例, 满足的方案必须遵循: 第一,四个字符相同, 第二,三个字符相同, 但是第一,二个字符不同, 所以有26*25=650种可行方案.