1478. [UVa 1362] 多叉树遍历

【题目描述】

考古学家在一个古埃及金字塔中发现了一系列隐藏的洞穴。通过翻译附近墙上的象形文字，人们掌握了这些洞穴的结构。在一个金字塔内有 $n$ 个由狭窄通道相连的洞穴，其中某个洞穴通过一条通道与外界连通。对于每个洞穴，从外界有且仅有一条通过通道进入该洞穴的路径。所有的洞穴都在金字塔的地下室中，因此我们可以认为它们都在同一水平面上。通道互不交叉。每一个洞穴的墙壁都被染成了某种颜色。

科学家们决定给洞穴绘制一张详细的地图，为此他们使用了一个探测机器人。这个机器人有两个元件：用以记录对每个洞穴描述的输出磁带，和一个操作栈。

最初机器人沿通道进入与外界直接相连的洞穴。当它第一次沿某条通道行走时，它将这条通道的特征放在栈顶。当它进入某个洞穴时，它将这个洞穴的颜色记录在输出磁带上。之后它将选择尚未经过的通道中最靠左的一个，并沿着这条通道继续前进。如果没有这样的通道，那么机器人就将栈顶元素弹出，沿着该通道以（与上一次经过该通道时的）反向行走。当机器人返回外界时它的任务就结束了。显然，机器人在一次旅行中至少经过每个洞穴各一次，并且以每个方向经过每个通道恰好一次。

科学家们已经把机器人派出去执行任务了。当它返回后，科学家们就开始研究输出磁带。他们失望地发现，一个输出磁带并不对应唯一的一个洞穴系统。现在他们有了一个新问题：可以有多少种洞穴系统对应输出磁带上的序列。请帮助他们解决这个问题。

因为答案可能很大，你应该输出它模 $1000000000$ 的值。请注意，洞穴的拓扑结构远比它们的绝对位置重要。因此图中的 $(c)$ 和 $(d)$ 被认为是两种不同的洞穴系统。

【输入格式】

输入包含多组数据。每组数据仅一行，即由大写字母组成的访问序列。序列非空，且长度不超过 $300$.输入结束标志为文件结束符($EOF$).

【输出格式】

对于每组数据，输出满足条件的多叉树的数目除以 $10^9$ 的余数。

【样例输入】

ABABABA

【样例输出】

5

【来源】

UVa1362 Exploring Pyramids NEERC 2005,LA3516

刘汝佳，《算法竞赛入门经典训练指南》表2.2