Kaavi and Magic Spell-cf-1336C

// https://www.youtube.com/watch?v=6OJdAemQSKo
string s,t;ll dp[3005][3005];int n,m;

ll giveres(int pos,int l){
    if(pos==-1) return 1ll;
    ll &ret = dp[pos][l];
    if(ret!=-1) return ret;
    ret = 0;
    if(l>=m||t[l]==s[pos]) ret = (ret + giveres(pos-1,l+1))%mod;
    if(pos+l>=m||s[pos]==t[l+pos]) ret = (ret + giveres(pos-1,l))%mod;
    return ret;
}

int main()
{
    booster()
    //read("input.txt");
    cin >> s >> t;
    ll ans = 0;
    n = s.size();m = t.size();
    mem(dp,-1);
    for(int i = m-1;i<n;i++) {
        ans = ans + giveres(i,0);
        if(ans>=mod) ans %= mod;
    }

    cout << ans << endl;

    return 0;
}