金字塔 (pyr.pas/c/cpp) 题目描述 虽然探索金字塔是极其老套的剧情，但是这一队 探险家还是到了某金字塔脚下。经过多年的研究，科 学家对这座金字塔的内部结构已经有所了解。首先， 金字塔由若干房间组成，房间之间连有通道。如果把 房间看做节点，通道看做边的话，整个金字塔呈现一 个有根树结构，节点的子树之间有序，金字塔有唯一 的一个入口通向树根。并且，每个房间的墙壁都涂有 若干种颜色的一种。 探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这 种机器人会从入口进入金字塔， 之后对金字塔进行深度优先遍历。 机器人每进入一个房间 （无 论是第一次进入还是返回） ，都会记录这个房间的颜色。最后，机器人会从入口退出金字塔。 显然， 机器人会访问每个房间至少一次， 并且穿越每条通道恰好两次 （两个方向各一次） ， 然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定金字 塔的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构 会得到这个序列。由于结果可能会非常大，你只需要输出答案对 109取模之后的值。 输入格式 输入文件包含一行，含有一个字符串，表示机器人得到的颜色序列。 输出格式 输出一个整数表示答案。 样例输入 ABABABA 样例输出 5 样例说明 有如下 5种方案。由于子树之间是有序的，所以(3)和(4)是两种不同的方案。 数据范围与约定 对于 24% 的数据，字符串的长度不超过 20。 对于 100% 的数据，字符串的长度不超过 300。