← 返回题目列表

AtCoder · jag2018summer_day2_h

H. 前缀后缀免费

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

给你一个字符串 S 由小写英文字母组成。 计算字符串的数量 T 满足以下所有条件:

  • T 是一个与以下长度相同的字符串 S,由小写英文字母组成。
  • 对于所有人 K ( 1 \leq K \leq |S| ),由第一个组成的字符串 K 字母 S 与最后一个形成的字符串不一致 K 字母 T.

由于答案可能非常大,因此求模数 10^9+7.

约束

  • 1 \leq |S| \leq 10^6
  • S 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

S

输出

打印满足条件的字符串数,取模 10^9+7.


示例输入 1

aa

示例输出 1

650

例如, T= zz 和 ab 满足条件,但是 ba or aa 没有。


示例输入 2

abc

示例输出 2

16873

示例输入 3

xrxbaxrxikxrxgvcpuwx

示例输出 3

352084595