Consider a DP (Dynamic Programming) where we define \(\mathrm{dp}[i][j] :=(\)the number of strings \(S\) such that \(|S|=i,|T|=j)\). Considering appending \(k\)-character fraction such that \(S_i \not = S_{i+1}\) and \(S_{i+1}=S_{i+2}=\dots =S_{i+k}\), we can see that the transition can be written as follows:

・\(\mathrm{dp}[i+k][j+1+(\)the number of digits of \(k)]+=dp[i][j] \times 25\ (1 \le k \le N)\).

However, the time complexity of this DP is \(\mathrm{O}(N^3)\). Here, there are \(\lceil \log_{10} (N+1) \rceil\) kinds of the number of digits of \(1+k\), so the DP can be optimized by processing the transitions with the number of digits of \(1+k\) being same at once and taking the cumulative sum while the DP. Now each transition costs \(\mathrm{O}(\log N)\) time, so the problem can be solved in a total of \(\mathrm{O}(N^2\log N)\) time. Sample code (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;
}