#P1595. 2023.09.22-企鹅music-第三题-塔子哥构造字符串

2023.09.22-企鹅music-第三题-塔子哥构造字符串

题目描述

塔子哥需要构造一个串 ss 为串 tt ，初始串 ss 为空。

每次操作

  • 他可以在串 ss 的末尾添加一个字母
  • 也可以选择当前串 ss 中的一个长度大于等于 22 的子串，添加到 ss 的末尾。

现在塔子哥想问你，一共有多少种不同的构造方案。

输出描述

一个只包含小写字母的字符串 tt ，tt 的长度不超过 300300

输出描述

一个整数，表示构造出 tt 的不同方案数。答案对 109+710^9+7 取模。

样例

输入

aaaa

输出

2

说明

"" --> "a" --> "aa" --> "aaa"，即前三个字符都必须通过末尾添加一个字母的方式
而对于 "aaaa" ，则可以通过 "aa" --> "aaaa" ，或者 "aaa" -> "aaaa" 的方式构造而来
故一共有 22 种方案。

知识点:*****

查看知识点以及同类型题目

Statistics