题目描述

有一棵森林，森林中有 $2n$ 棵树，每棵树都有 $2n$ 层，除叶节点以外，每个节点都有 $2n$ 个儿子。

你一开始在第一棵树的根节点上。给出一个长度为 $n$ 的序列，如果是 s 表示走到儿子，b 表示走到下一个兄弟，z 表示走回上一个点（如果没有则忽略）。现在你可以任选这个序列的一个子序列执行（包含空序列），问你可能到达的节点有多少个。

输入格式

一行，一个长度为 $n$（$\le 10^5$）的字符串。

输出格式

一行，一个整数，表示能够到达的节点数 $\bmod (10^9+7)$ 的值。

输入样例

sbz

输出样例

4

样例说明

空串、sz、bz、z 到达同一个点，s、sbz 到达同一个点，b 到达一个点，sb 到达一个点。一共可能达到 $4$ 个点。

子任务

对于 $30\%$ 的测试数据，满足 $n \le 5$。

对于另外 $20\%$ 的测试数据，满足 $n \le 10$。

对于另外 $20\%$ 的测试数据，满足输入串中不含 z。

对于所有的测试数据满足 $n \le 10^5$。