Untitled

#define mod 1000000007
 
long long dp[2222][2222];
char buf[2222];
string s;
 
long long sum1[2222];
long long sum2[2222][2222];
 
bool used[2222];

int Solution::solve(int A, int B, String C){
    int n=A, k=B;
    s = C;
 
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            memset(used, false, sizeof(used));
            dp[i][j] = (s[i] - 'a') * dp[i + 1][j];
            if (j - (n - i) >= 0) dp[i][j] += ('z' - s[i]) * dp[i + 1][j - (n - i)];
 
            for (int l = n - 1; l > i; l--) {
                used[l] = true;
                if ((n - l) * (l - i + 1) <= j)
                    dp[i][j] += ('z' - s[l]) * dp[l + 1][j - (n - l) * (l - i + 1)];
                else
                    break;
            }
            for (int l = i + 1; l < n; l++) {
                if (used[l]) break;
                if ((n - l) * (l - i + 1) <= j)
                    dp[i][j] += ('z' - s[l]) * dp[l + 1][j - (n - l) * (l - i + 1)];
                else
                    break;
            }
            dp[i][j] += sum1[j];
            if (j == 0) dp[i][j]++;
            dp[i][j] %= mod;
            
            sum1[j] = (sum1[j] + (s[i] - 'a') * dp[i + 1][j]) % mod;
        }
    }
    cout << dp[0][k] << endl;
    return 0;
}