#CS1080. 空字符串

空字符串

题目背景

翻译自 CSES-1080 题。

题目描述

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

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

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

输入格式

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

输出格式

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

样例

aabccb

3

说明/提示

$1 \leq n \leq 500$