\(y[i]\) 为以第 \(i\) 个词结尾，\(l[i]\) 为第 \(i\) 个词长度。

设状态 \(f[i][j]\) 为长度 \(i\) 的，以 \(j\) 为结尾的一句诗的方案数，则

\(f[i][Y]=\sum_{y[i]=Y}\sum_{x=1}^{n}f[i-l[j]][x]\)

发现后面那一坨可以预处理，设

\(g[i]=\sum_{x=1}^{n}f[i][x]\)

\(g[i]\) 的意义是长度为 \(i\) 的一句诗的方案数，显然可以无限背包 \(O(nk)\) 求。

\(g[i]=\sum_{j=1}^{n}g[i-l[j]]\)

那么: \(f[i][Y]=\sum_{y[j]=Y}g[i-l[j]]\)

对于每个需要的押韵{'A','B',……}答案就等于：

\(Ans[i]=\sum_{j=1}^{n}f[k][k]^cnt[i]\)

然后输出 \(\prod_{i='A'}^{'Z'}Ans[i]\)。