855. 神秘单词

单点时限: 2.0 sec

内存限制: 512 MB

有一个电视直播节目,其中有一个神秘单词 $W$,猜中单词的人可以获得大奖,但是要完全猜中一个单词太难了,所以节目组决定放宽一下条件。

如果你猜的单词中每个字母,都至少和神秘单词中相同位置相差不超过一个位置的字母相同,就可以获得一份小奖。

形式化的说,对于一个猜的单词 $G$,获奖的条件为 $(|G|=|W|)\land \forall~i~((1 \leq i \leq |G|) \rightarrow \exists~j~((\max(1, i-1) \leq j \leq \min(i+1, |G|))\land(G_i=W_j)))$,其中 $G_i$ 表示字符串 $G$ 中的第 $i$ 个字母(字符串$G$中的第1个字母下标为1),$|G|$表示字符串$G$的长度。

节目组想知道对于一个指定的神秘单词 $W$ 有多少种可能获奖的猜测单词(包括大奖和小奖),因为可能的单词数量太多了,他们想知道答案对 $1~000~000~007$ 取模的结果。

输入格式

神秘单词 $W$($1 \leq |W| \leq 1~000$),保证单词全部由小写英文字母构成。

其中 10% 的数据保证 $|W| \leq 10$。

输出格式

输出可能中奖的单词数量对 $1~000~000~007$ 取模后的结果。

样例

Input
yes
Output
12
Input
y
Output
1
Input
yy
Output
1

提示

对于神秘单词 yes,所有可以获奖的单词包括:

yes, yys, yss, yee, yye, yse, ees, eys, ess, eee, eye, ese

280 人解决,348 人已尝试。

342 份提交通过,共有 1895 份提交。

2.8 EMB 奖励。

创建: 6 年,4 月前.

修改: 4 年,10 月前.

最后提交: 2 月,4 周前.

来源: N/A

题目标签