虽然探索金字塔是极其老套的剧情,但是有一队探险家还是到了某金字塔脚下,经过多年的研究,科学家对这座金字塔的内部结构已经有所了解,首先,金字塔由若干房间组成,房间之间连有通道,探险队员打算进一步了解金字塔的结构,为此,他们使用了一种特殊设计的机器人,这种机器人会从入口进入金字塔,之后对金字塔进行深度优先遍历,最后,机器人会从入口退出金字塔,但是,探险队员发现这个颜色序列并不能唯一确定金字塔的结构。
虽然探索金字塔是极其老套的剧情,但是有一队探险家还是到了某金字塔脚下。 经过多年的研究,科学家对这座金字塔的内部结构已经有所了解。 首先,金字塔由若干房间组成,房间之间连有通道。 如果把房间看作节点,通道看作边的话,整个金字塔呈现一个有根树结构,节点的子树之间有序,金字塔有唯一的一个入口通向树根。 并且,每个房间的墙壁都涂有若干种颜色的一种。 探险队员打算进一步了解金字塔的结构,为此,他们使用了一种特殊设计的机器人。 这种机器人会从入口进入金字塔,之后对金字塔进行深度优先遍历。 机器人每进入一个房间(无论是第一次进入还是返回),都会记录这个房间的颜色。 最后,机器人会从入口退出金字塔。 显然,机器人会访问每个房间至少一次,并且穿越每条通道恰好两次(两个方向各一次), 然后,机器人会得到一个颜色序列。 但是,探险队员发现这个颜色序列并不能唯一确定金字塔的结构。 现在他们想请你帮助他们计算,对于一个给定的颜色序列,有多少种可能的结构会得到这个序列。 因为结果可能会非常大,你只需要输出答案对 10^9 10 9 取模之后的值。
(图片来源网络,侵删)