Input: s = "bccb"
Output: 6

public class Solution {
    public int CountPalindromicSubsequences(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        int[,] dp = new int[n, n];

        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j]) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s[l] != s[i]) l++;
                    while (l <= r && s[r] != s[j]) r--;
                    
                    if (l > r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 1;
                    } else {
                        dp[i, j] = dp[i + 1, j - 1] * 2 - dp[l + 1, r - 1];
                    }
                } else {
                    dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1];
                }

                dp[i, j] = (dp[i, j] + MOD) % MOD;
            }
        }

        return dp[0, n - 1];
    }
}

dotnet nuget locals global-packages --clear

dotnet nuget locals http-cache --clear

dotnet nuget locals temp --clear

dotnet nuget locals all --clear

dotnet nuget locals all --list