問題文と同様に辞書順で \(i\) 番目の英大文字を \(a_i\) とおきます。

文字列のうち z が出現する個数ごとに条件を満たす文字列の個数を求め、これらを足し合わせることで答えを求めることを考えます（説明の都合上 z の個数ごとに考えていますが、z であることは本質ではなく、\(1\) つのアルファベットを使う個数ごとに考えると捉えてよいです）。

長さ \(s\) の文字列中に z が \(t\) 個存在するとします。このとき、z の位置の決め方が \(\binom{s}{t}\) 通りあります。z 以外の部分については、z を除いた長さ \(s-t\) の文字列を考えることによって \(\binom{s}{t}\) 通りそれぞれに対し、 z を含まない長さ \(s-t\) の文字列であって \(a_i\) が \(0\) 個以上 \(C_i\) 個以下であるものが対応していることがわかります。

したがって a, b, \(\ldots\), z について考えていたものを a, b, \(\ldots\), y について帰着できることがわかりました。

同様に考えると、a, b, \(\ldots\), y についての問題は a, b, \(\ldots\), x について帰着でき、これを繰り返すことにより本問題を解くことができそうだと考えられます。

このように小さいサイズに問題を帰着できたときには dp が有効なことが多いです。

実際、\(dp_{i,j}\) を \(a_1, a_2, \ldots, a_i\) からなる長さ \(j\) の文字列であって、各 \(1 \leq k \leq i\) に対して \(a_k\) が \(0\) 個以上 \(C_k\) 個以下であるものの個数とおくと、上の考察から \(dp_{i + 1, j} = \sum_{k = 0}^{\min(j, C_{i+1})} dp_{i,j-k} \binom{j}{k}\) となります（\(a_{i + 1}\) の個数を \(k\) として \(k\) ごとに足し合わせています）。

答えは \(\sum_{j= 1}^{K}dp_{26, j}\) であり、dp は \(j \leq K\) の範囲で計算すれば十分であることに注意してください。

二項係数を階乗およびその逆元の前計算、あるいはパスカルの三角形の要領で二項係数自体を前計算することでこの dp は文字の種類数を \(\sigma\) とおいて（本問題では \(\sigma = 26\) です）時間計算量 \(O(\sigma K^2)\) で計算することができ、本問題の制約下では十分高速です。

実装例 (C++)