问题描述

考古学家在埃及金字塔中发现了一组新的隐藏洞穴。附近墙壁上的象形文字表明，洞穴的结构如下：金字塔中有 $n$ 个洞穴，通过狭窄的通道连接，其中一个洞穴与外部世界相连。通道系统组织得非常巧妙，使得从外部到每个洞穴都有且仅有一条路径。所有洞穴都位于金字塔的地下室，可以认为它们位于同一平面。通道不会相交。每个洞穴的墙壁都被涂成一种颜色。

科学家们决定创建一个更详细的洞穴描述，因此他们计划使用一个探索机器人。机器人有两种内存：

• 输出带：用于记录洞穴的描述。
• 操作内存：组织成一个栈。

机器人首先通过通道进入与外部世界相连的洞穴。当它第一次沿任何通道旅行时，它会将通道的描述放在栈的顶部。当机器人进入任何洞穴时，它会将洞穴墙壁的颜色打印到输出带上。之后，它选择最左边的未旅行过的通道并沿其前进。如果没有这样的通道，机器人会从栈的顶部取出通道描述并沿其反向旅行。机器人的任务在它返回到金字塔外部时结束。可以很容易地看出，在其旅行过程中，机器人至少访问每个洞穴一次，并且沿每个通道在每个方向上恰好旅行一次。

科学家们已经将机器人送去执行任务。在机器人返回后，他们开始研究输出带。令他们失望的是，他们发现输出带并不能唯一地描述洞穴系统。现在他们面临一个新问题：他们想知道有多少种不同的洞穴系统可能产生他们拥有的输出带。帮助他们找出答案。

由于请求的数字可能非常大，你应该输出它模 $1,000,000,000$ 的结果。请注意，洞穴的绝对位置并不重要，但它们的相对位置很重要，因此在下图中，洞穴 (c) 和 (d) 被认为是不同的。

输入

输入是科学家们获得的输出带，即机器人访问洞穴时墙壁颜色的序列。颜色用大写英文字母表示。输出带的长度不超过 300 个字符。

输出

输出一个整数——可能产生给定输出带的洞穴系统的数量（模 $1,000,000,000$）。

示例输入与输出

示例输入 1

ABABABA

示例输出 1

5

示例输入 2

AB

示例输出 2

0

来源

Northeastern Europe 2005