解题思路

1. 问题转化：每个音节必须是 $s$ 的排列，因此只需关心 $s$ 中至多 3 种字母的相对顺序。把 $s$ 里出现过的字母按首次出现顺序映射成整数 $0,1,2$。
2. 状态：设 dfs(i, x, y, z) 表示：当前音节映射为 $(x,y,z)$，还需要组成总长为 $i$ 的音节序列时的方案数。当 $i=1$ 时只剩当前音节，方案数为 1。
3. 接龙转移：下一个音节必须是同一多重集的排列，且首字母等于当前音节的末字母 $z$。
   • 若 $x \neq y$，以 $z$ 开头的排列有两种：$(z,x,y)$ 与 $(z,y,x)$，方案数为二者之和。
   • 若 $x = y$，只剩一种：$(z,x,y)$。
4. 记忆化：把 $(x,y,z)$ 编码为 $x + 3y + 9z$，对每个剩余长度 $i$ 存入哈希表，避免重复搜索。每组数据单独清空记忆化表。答案对 $10^9+7$ 取模。