Субпалиндромы (с for)

#include <bits/stdc++.h>

using namespace std;

const int N = 5005;
const int mod = 29876543;

int n;
int dp[N][N];
string s;

//int get(int l, int r) {
//    if (l > r) return 0;
//    if (l == r) return 1;
//    if (dp[l][r] > 0) return dp[l][r];
//    int ans = 0;
//    int a1 = get(l, r - 1);
//    int a2 = get(l + 1, r);
//    int a3 = get(l + 1, r - 1);
//    ans = (ans + a1) % mod;
//    ans = (ans + a2) % mod;
//    ans = (ans - a3) % mod;
//    if (ans < 0) ans += mod;
//    if (s[l] == s[r]) {
//        ans += get(l + 1, r - 1) + 1;
//        ans %= mod;
//    }
//    dp[l][r] = ans;
//    return ans;
//}

int main(){
    cin >> s;
    n = s.size();
    s = ' ' + s;

    for (int r = 1; r <= n; r++) {
        for (int l = r; l >= 1; l--) {
            if (l == r) {
                dp[l][r] = 1;
                continue;
            }
            dp[l][r] = (dp[l][r] + dp[l][r - 1]) % mod;
            dp[l][r] = (dp[l][r] + dp[l + 1][r]) % mod;
            dp[l][r] = (dp[l][r] - dp[l + 1][r - 1]) % mod;
            if (dp[l][r] < 0)
                dp[l][r] += mod;
            if (s[l] == s[r]) {
                dp[l][r] = (dp[l][r] + dp[l + 1][r - 1] + 1) % mod;
            }
        }
    }

    cout << dp[1][n] << endl;
}