字典树 复杂度 $O(N^2S)$ $S$为字符集大小，也可以改到$O(N^2logS)$。

注意到在下标 $i$ 往右移动的时候，字典树内索引是否合法具有单调性，考虑对树中每一个节点维护一个指针 $curidx[u]$ 来把复杂度均摊到 $O(N^2S)$

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")

题目描述

小红需要构造一个串 $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$ 种方案。