遍历 (dfs)

【题目描述】

​ 007被困在了一个树形迷宫中。

​ 他此时处在的点，在他的认知中，是这棵树的根节点。

​ 007有一种特殊的能力，他不会重复探索同一个房间，并且每次他都会选择最左边第一个没有探索过的房间进行探索，如果没有，他就退回上一个房间，最后他会回到最初的房间

​ 每个房间都有标记，但是标记可能重复，007将这些标记按顺序记录了下来。

​ 现在007已经有了这个标记序列，他希望知道，这个迷宫的形状有多少种可能（答案对1e9+7取模)

【输入格式】

一个只包含小写字母的字符串，表示007得到的序列

【输出格式】

一个整数，表示答案

【样例 $1$ 输入】

ababa

【样例 $1$ 输出】

2

【样例 $2$】

见下发文件

【数据范围】

令$n$表示字符串长度

对于$30\%$的数据，$1\le n\le 10$。

对于$100\%$的数据，$1\le n\le 300$。