\(\mathrm{dp}[i][j] :=(|S|=i,|T|=j\) となる文字列 \(S\) の個数 \()\) と定義した動的計画法を考えます。 \(S_i \not = S_{i+1}\) かつ \(S_{i+1}=S_{i+2}=\dots =S_{i+k}\) となる \(k\) 文字の部分を追加することを考えると、遷移は以下のようになります。

・\(\mathrm{dp}[i+k][j+1+k\) の桁数\(]+=dp[i][j] \times 25\ (1 \le k \le N)\)

ですが、このままでは計算量が \(\mathrm{O}(N^3)\) となってしまいます。 ここで、\(1 + k\) の桁数は \(\lceil \log_{10} (N+1) \rceil\) 種類の値しかとらないため、\(1+k\) の桁数が同じ遷移をまとめ、かつ累積和を取りながら動的計画法をすることで高速化できます。 これにより \(1\) 箇所の遷移を \(\mathrm{O}(\log N)\) でできるため、計算量 \(\mathrm{O}(N^2\log N)\) でこの問題を解くことができます。 実装例(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }

ll dp[3101][3101];
ll sum[3101][3101];
int main() {
  ll n,p;
  cin>>n>>p;
  dp[0][0]=modPow(25,p-2,p)*26ll%p;
  vector<ll> ten={1,10,100,1000,10000,100000};
  for(int i=1;i<=n;i++) sum[0][i]=dp[0][0];
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      for(int k=1;k<=4;k++){
        if(i-k-1<0) continue;
        ll x=max(j-ten[k-1]+1,0ll),y=max(j-ten[k]+1,0ll);
        dp[i][j]+=(sum[i-k-1][x]-sum[i-k-1][y]+p)*25;
        dp[i][j]%=p;
      }
      sum[i][j+1]=sum[i][j]+dp[i][j];
      sum[i][j+1]%=p;
    }
  }
  ll sum=0;
  for(int i=1;i<n;i++) sum+=dp[i][n];
  cout<<sum%p<<endl;
}