簡単のため \(K\) を \(N-K\) で置き換えます。ここで、条件は「部分列から独立に ABC を取れる個数の最大値が \(K\)」と同値です。証明は「文字列 \(S\) から複数文字を消して部分列に ABC が取れないようにするために必要な消す文字数の最小値」と「文字列 \(S\) から独立に ABC が取れる個数の最大値」を求めようとすると両方以下のコードのようになることから従います。

int A=0,AB=0,ABC=0;
for(int i=0;i<S.size();i++){
  if(S[i]=='A') A++;
  if(S[i]=='B') AB=min(AB+1,A);
  if(S[i]=='C') ABC=min(ABC+1,AB);
}

以降、ABC が独立に \(K\) 個取れる文字列の数え上げを考えます。(\(K+1\) 個以上取れてもいいものとします。) また、\(N\) を \(N-3K\) で置き換えます。ここで、文字列 \(S\) を見たときに前から貪欲に ABC を独立に \(K\) 個取ることを考えます。すると、ABC が \(K\) 個混ざった文字列が現れます。例えば、

• ABABCBAAC は前から貪欲に構成すると \(1,2,5\) 文字目と \(3,4,9\) 文字目の \(2\) 個の ABC が取れ、この部分だけ元の文字列から抜き出すと ABABCC が取れる。

このような文字列を固定して数え上げを行いましょう。すると、各文字の間(もしくは先頭か末尾)に合計 \(N\) 文字を挿入することになりますが、各間について挿入できる文字の種類は \(0,1,2,3\) 種類のいずれかとなります。よって、母関数として \(\frac{1}{(1-x)^p(1-2x)^q(1-3x)^r}\) という表示を持つことになります。

この母関数を、ABC \(K\) 個からなる貪欲結果としてあり得る全ての文字列について和を取ることを考えます。すると、\(p \le 3K,q \le 3K,r = 1\) が簡単に分かるため総和は \(\frac{f(x)}{(1-x)^{3K}(1-2x)^{3K}(1-3x)}\) という表示を持つことが分かります。(\(p,q\) はこれより定数倍よく上界を取ることが出来ますが、省略します。) \(f(x)\) を直接 dp で求めることも出来ますが、上のコードでの i,A,AB,ABC を key に持って dp をすることで先頭の項を得てそこから \(f(x)\) を復元することが出来ます。このパートの計算量は \(\mathrm{O}(K^4)\) です。

各クエリに回答するために、\(\frac{f(x)}{(1-x)^{3K}(1-2x)^{3K}(1-3x)} = \frac{f_1(x)}{(1-x)^{3K}} + \frac{f_2(x)}{(1-2x)^{3K}} + \frac{f_3(x)}{1-3x}\) という部分分数分解結果を保持します。部分分数分解で \(g(x)(1-2x)^n= 1 \bmod (1-x)^m\) などを満たす \(g(x)\) を得たくなりますが、これは多項式でユークリッドの互除法を行ってもよいですし、\(y = 1-x\) と変数変換し \(g(x)(-1+2y)^n = 1 \bmod y^m\) と変形し \(g(x) = (-1+2y)^{-n}\) として \(g(x)\) を \(y\) の \(m\) 次式で表してから変数変換を戻す、などといった方法もあります。

部分分数分解さえ出来れば各クエリに \(\mathrm{O}(K)\) で答えることは簡単です。よって、この問題を \(\mathrm{O}(K^4 + QK)\) で解くことが出来ます。(二項係数を \(\mathrm{O}(N+K)\) かけて前計算することも許されます。)