Code : Paths to a Goal

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const int L = 0, R = 1;

using mint = modint1000000007;

mint solve(string &str, int bound, int src, int target) {
    int n = str.length();

    vector<vector<mint>> dp(bound + 5, vector<mint>(2, 0));
    // dp[pos][ch] is the number of unique subsequences to reach pos when the
    // last character is ch.

    for (char ch : str) {
        auto ndp = dp;
        for (int pos = 0; pos <= bound; pos++) {
            mint sum = dp[pos][L] + dp[pos][R];
            if (ch == 'l' && pos) {
                ndp[pos - 1][L] = sum;
            }
            if (ch == 'r') {
                ndp[pos + 1][R] = sum;
            }
        }
        if (ch == 'l' && src) {
            ndp[src - 1][L] += 1;
        }
        if (ch == 'r') {
            ndp[src + 1][R] += 1;
        }

        swap(dp, ndp);
    }

    // Empty sequence needs to be counted separately.
    return (src == target) + dp[target][L] + dp[target][R];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string str;
    cin >> str;
    int bound;
    cin >> bound;
    int src, target;
    cin >> src >> target;
    cout << solve(str, bound, src, target).val() << "\n";
    return 0;
}