思路：动态规划

$f[i]$ 表示构造出 $t$ 的前 $i$ 个字符的不同方案数。

• 在末尾添加第 $i$ 个字符：$f[i]=f[i] + f[i-1]$

题目描述

小红需要构造一个串 $s$ 为串 $t$ ，初始串 $s$ 为空。

每次操作

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

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

输出描述

一个只包含小写字母的字符串 $t$ ，$t$ 的长度不超过 $300$

输出描述

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

样例

输入

aaaa

输出

2

说明

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