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

板块: Counting Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

计算重排一个字符串中字符的方式数，使得任意两个相邻字符都不相同。

例如，aabc 的答案是 $6$，因为可能的顺序有 abac、abca、acab、acba、baca 和 caba。

输入

唯一的一行输入包含一个由 $n$ 个介于 a–z 之间的字符组成的字符串。

输出

输出一个整数：答案对 $10^9+7$ 取模。

数据范围

$1 \le n \le 5000$

样例输入

aabc

样例输出

6