Очевидно, что от строки $s$ нам нужно только количество вхождения каждого символа в строку.

1. Двумерная динамика. Состояние $d{p}_{sym,sz}$ — количество строк длины $sz$ собранных из символов алфавита $\le sym$. Динамику считаем вперёд.
2. Начальные состояния — $dp[0][0]=1$
3. $d{p}_{sym+1,sz}={\sum }_{k=0}^{k\le min(sz,cnt[sym])}d{p}_{sym,sz-k}\times \left(\genfrac{}{}{0ex}{}{sz}{k}\right)$

Объяснение пересчёта :

Мы зафиксировали строку длины $sz-k$ из $sym$ первых букв, а дальше докинем $k$ символов в эту строку на любую из $sz$ позиции.

Почему $sz$? Можно представить как будто мы держим строку длины $sz$ и в пустые окошки расставляем.

4. Ответ — $\sum dp[26][.]$

Сложность $O(n^2)$ так как частота всех букв равна длине строки.

vector<vector<int>> dp(26 + 1, vector<int>(n + 1));
dp[0][0] = 1;
for (int sym = 0; sym < 26; sym++) {
  for (int sz = 0; sz <= n; sz++) {
    for (int k = 0; k <= min(sz, cnt[sym]); k++) {
      dp[sym + 1][sz] = add(dp[sym + 1][sz], mult(dp[sym][sz - k], cnk(sz, k)));
    }
  }
}

int ans = 0;
for (int i = 1; i <= n; i++) {
  ans = add(ans, dp[26][i]);
}
cout << ans;