题目描述

探险队员们顺利乘坐升降梯来到了塔顶。塔顶有若干房间，房间之间连有通道。如果把 房间看做节点，通道看做边的话，整个塔顶呈现一个有根树结构，并且每个房间的墙壁都涂 有若干种颜色的一种。

现在探险队员们在树根处，他们打算进一步了解塔顶的结构，为此，他们使用了一种特 殊设计的机器人。这种机器人会从队员身边，也就是树根出发，之后对塔顶进行深度优先遍 历。机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。最 后，机器人会回到树根。

显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定塔顶 的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会 得到这个序列。由于结果可能会非常大，你只需要输出答案对 $\red{10^9 }$取模之后的值。

输入格式

输入文件包含一行，含有一个字符串，表示机器人得到的颜色序列。

输出格式

输出一个整数表示答案。

样例

输入样例

ABABABA

输出样例

5

提示

样例说明

有如下 $\red{5 }$种方案。注意子树之间是有序的，所以$\red{(3)}$和$\red{(4)}$是两种不同的方案。

数据范围与约定

对于 $\red{24\% }$的数据，字符串的长度不超过 $\red{20}$。

对于 $\red{100\% }$的数据，字符串的长度不超过 $\red{300}$。