本番で「簡単じゃーん」とか言ってたら、解説と違う解法だったので

言いかえ・余事象

操作を逆から見ると、「長さ $|S|+K$ で、部分列に $S$ を持つ文字列」の個数を求めればいいことがわかります。（Editorialではこれを直接求めていますが、僕にはこれを直接求めるのが困難に感じたので、余事象を考えました。）

余事象を考えると、「長さ $|S|+K$ で、部分列に $S$ を持たない文字列 $T$ 」の個数がわかればいいです。

余事象を解く

$L$ を、「 $T$ の部分列かつ $S$ の接頭辞である最長の文字列の長さ」とします。

$0\le L \lt |S|$ なので、各 $L$ について $O(1)$ で求められれば良いです。

$p_i$ を、「 $p_{i-1}\lt j$ かつ $T_j=S_i$ となる最小の $j$ 」とします。

$p$ の選び方は ${}_{|S|+K}C_L$ 通りあります。

$T$ の $p$ として採用されないindex $i$ の、文字の選び方を考えます。 $i\lt p_j$ となる最小の $j$ を考えたとき、 $S_{p_j}$ は $T_i$ として使えません。

逆にそれ以外の文字は使えるので、 $26-1=25$ 通りの文字を選べます。

よって、各 $L$ について ${}_{|S|+K}C_L\times 25^{|S|+K-L}$ を足し合わせればいいです。

なんか説明が苦手なので駄文になってしまった気がしています。

考察はどっちが楽かわかりませんが、僕には余事象の方が簡単に感じます。あと、実装は明らかにこっちのほうが楽です（どっちでも楽だろ）。