First, we ignore the templates and only count the number of sequences of form-~k~.

Let ~A[i][k][\alpha]~ denote the number of sequences of form-~k~ of length ~i~ beginning with ~\alpha~. Note that if the second character ~\beta~ comes before ~\alpha~, possible sequences of form-~k~ are those constructed by concatenating ~\alpha~ with form-~(k-1)~ sequences beginning with ~\beta~. On the other hand, if ~\beta~ is ~\alpha~ or comes after ~\alpha~, we can concatenate ~\alpha~ with any form-~k~ sequence.

Thus, we have the following recurrence:

$$\displaystyle A[i][k][\alpha] = \sum_{\beta \ge \alpha} A[i-1][k][\beta] + \sum_{\beta < \alpha} A[i-1][k-1][\beta]$$

This idea can be extended to count the number of sequences that also match the templates. Table ~A~ can be computed in time ~\mathcal O(MK)~.

Given ~A~, we can trace back the computation of ~A~ to find the required ~R~-th gene sequence.