题目背景

翻译自 CSES-1080 题。

题目描述

给定一个由 $n$ 个字符（范围从 $a$ 到 $z$）组成的字符串。

在每一步，你可以移除任何两个相邻且相同的字符。你的目标是通过移除所有字符，构造一个空字符串。

你可以用多少种方法完成这一过程？

输入格式

唯一的输入行包含一个长度为 $n$ 的字符串。

输出格式

输出一个整数：表示完成此过程的方法数，结果对 $10^9 + 7$ 取模。

样例

aabccb

3

提示

aabccb 有三种移除方式：

方式1：

• 第一步：移除中间的 cc → 得到 aabb
• 第二步：移除中间的 aa → 得到 bb
• 第三步：移除 bb → 空

方式2：

• 第一步：移除中间的 cc → 得到 aabb
• 第二步：移除最后的 bb → 得到 aa
• 第三步：移除 aa → 空

方式3：

• 第一步：移除开头的 aa → 得到 bccb
• 第二步：移除 cc → 得到 bb
• 第三步：移除 bb → 空

数据范围

• $1 \le n \le 500$