题目描述

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

在每一步，你可以移除任何两个相邻且相同的字符。你的目标是通过移除所有字符，构造一个空字符串。你可以用多少种方法完成这一过程？

输入格式

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

输出格式

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

输入数据 1

aabccb

输出数据 1

3

说明/提示

1≤n≤500。

样例解释：

"aabccb" 有三种移除方式： 方式1: 第一步：移除中间的 "cc" -> 得到 "aabb" 第二步：移除中间的 "aa" -> 得到 "bb" 第三步：移除 "bb" -> 空 方式2: 第一步：移除中间的 "cc" -> 得到 "aabb" 第二步：移除最后的 "bb" -> 得到 "aa" 第三步：移除 "aa" -> 空 方式3: 第一步：移除开头的 "aa" -> 得到 "bccb" 第二步：移除 "cc" -> 得到 "bb" 第三步：移除 "bb" -> 空