以下のようなdpを考えます。

  • dp[i][j]=idp[i][j]=i 番目まで決めて810810...810 のうち jj 文字目まで出てくる通り数

毎回 M+1M+1 通り遷移先を求めていると O(MNK)O(MNK) になってTLEしてしまいます。
遷移先が制約下では j,j+1,j+2,j+3j,j+1,j+2,j+344 通りしかありえないことと、jjmod 3mod\ 3 で等しいなら j,j+1,j+2,j+3j,j+1,j+2,j+3 へ遷移する個数の分布も等しいことを利用します。
予め mod 3mod \ 30,1,20,1,2 の場合のそれぞれについてこの分布を計算しておくことで、遷移が O(1)O(1) で出来るようになり、計算量が O(M+NK)O(M+NK) になって間に合います。