在遥远的 LQ 国，只存在三种字符：、 和 （ASCII 码分别为 、、），所有的单词都由这三种字符组合而来。小蓝为了更加快速的记忆单词，决定将词典上所有的单词按照单词前缀将其分为 类，具体的要求是:
- 选出 个不同的单词前缀作为 类；
- 对于字典上的每个单词，只能属于 类中的某一个类，不能同时属于多个类；
- 对于 类中的每个类，至少包含有一个单词。
现在已知字典上一共有 个单词，小蓝想要知道将这 个单词按照上述要求分为 类，一共有多少种不同的方案。两个方案不同指的是两个方案各自选出的 个单词前缀不完全相同。答案可能过大，所以你需要将答案对 （即 ）取模后输出。
