#885. 字符串变换

字符串变换

样例下载

题目描述

对于一个字符串,你通过以下方式对其进行变换:

  • 步骤 1. 你选择删除其某个非空前缀,或者选择删除其某个非空后缀。注意,你只能删除字符串的前缀或后缀其一,且不能删光整个字符串。

  • 步骤 2. 你将剩余字符串复制粘贴到原字符串的前面或后面,得到一个新的字符串。注意:你只能粘贴到原字符串的前面或后面其一。

对于得到的新字符串,你可以对其继续重复以上操作。

你可以重复任意次。

现在给出最后得到的字符串 T,问:你有多少种可能的变换方案?答案可能很大,你需要将答案 mod 10910^9 后输出。

如果你没有读懂题目,请看样例解释。

输入格式

一个字符串 T

输出格式

一个整数,表示答案 mod 10910^9

输入样例

AAAA

输出样例

20

样例解释

对于字符串 AAA:

第一种:对于 AAA ,删除前缀 AA 剩余 A 放到 AAA 前面,得到 AAAA。

第二种:对于 AAA ,删除前缀 AA 剩余 A 放到 AAA 后面,得到 AAAA。

第三种:对于 AAA ,删除后缀 AA 剩余 A 放到 AAA 前面,得到 AAAA。

第四种:对于 AAA ,删除后缀 AA 剩余 A 放到 AAA 后面,得到 AAAA。

对于字符串 AA :

删除前缀 A 剩余 A 放到 AA 前面得到 AAA,然后接下来会有对于 AAA 的四种方案,最后得到 AAAA。

删除前缀 A 剩余 A 放到 AA 后面得到 AAA,然后接下来会有对于 AAA 的四种方案,最后得到 AAAA。

删除后缀 A 剩余 A 放到 AA 前面得到 AAA,然后接下来会有对于 AAA 的四种方案,最后得到 AAAA。

删除后缀 A 剩余 A 放到 AA 后面得到 AAA,然后接下来会有对于 AAA 的四种方案,最后得到 AAAA。

除此之外,你找不到其它的字符串可以通过以上变换方式可以得到 AAAA。

数据范围

|T| ≤ 100,保证字符串 T 全部由大写英文字母构成