#CS2421. 计数重排

计数重排

题目背景

翻译自 CSES-2421 题。

题目描述

计算可以重排字符串中字符的方式，使得没有两个相邻的字符相同。

例如，字符串 aabc 的答案是 6，因为可能的排列是：abac, abca, acab, acba, baca 和 caba。

输入格式

唯一的输入行是一个字符串，字符串由 n 个字符组成，字符范围为 a 到 z。

输出格式

输出一个整数：答案对 109+710^9 + 7109+7 取模。

样例

aabc

6

说明/提示

$1 \leq n \leq 50$