题目内容

小红有一个长度为$3$的字符串$s[1]$。

她希望在其基础上增加$n-1$个字符串，使得对于任意$i∈[2,n]$都满足$s[i][0] = s[i- 1][2]$，且每个字符串的长度以及所包含的字母种类和对应的数量都相同，我们称这个$n$个字符串构成同质接龙串。

题面描述

小红有一个长度为 $3$ 且仅由小写字母组成的字符串 $s(1)$。她想基于这个字符串，构造一个总共包含 $n$ 个字符串的序列 $s(1), s(2), \dots, s(n)$，要求如下：

1. 同质性：序列中每个字符串都与 $s(1)$ 的字母种类和对应数量相同（可视为 $s(1)$ 的任意排列）。
2. 接龙性：对于任意 $i$（$2 \leq i \leq n$），需满足 $s(i)$ 的首字母等于 $s(i-1)$ 的末字母。

请你计算，在给定初始字符串 $s(1)$ 和整数 $n$ 的条件下，满足上述要求的不同序列方案有多少种。若两种方案中存在某个位置的字符串不同，则视为两种不同方案。最终答案可能很大，请对 $10^9+7$ 取模后输出。

思路