链接: https://cses.fi/problemset/task/1080

板块: Counting Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个由 $n$ 个介于 a 到 z 之间的字符组成的字符串。

每一步，你可以删除任意两个相等的相邻字符。你的目标是通过删除所有字符来构造一个空字符串。

有多少种不同的删除方式？

输入

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

输出

输出一个整数：方式数量对 $10^9+7$ 取模。

数据范围

$1 \le n \le 500$

样例输入

aabccb

样例输出

3