The bear has a string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">|*s*|</sub> (record |*s*| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices *i*, *j* (1 ≤ *i* ≤ *j* ≤ |*s*|), that string *x*(*i*, *j*) = *s*<sub class="lower-index">*i*</sub>*s*<sub class="lower-index">*i* + 1</sub>... *s*<sub class="lower-index">*j*</sub> contains at least one string "bear" as a substring.

String *x*(*i*, *j*) contains string "bear", if there is such index *k* (*i* ≤ *k* ≤ *j* - 3), that *s*<sub class="lower-index">*k*</sub> = *b*, *s*<sub class="lower-index">*k* + 1</sub> = *e*, *s*<sub class="lower-index">*k* + 2</sub> = *a*, *s*<sub class="lower-index">*k* + 3</sub> = *r*.

Help the bear cope with the given problem.
The first line contains a non-empty string *s* (1 ≤ |*s*| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int MOD = 1e9+7;

long long ways[1000001];
bool ready[1000001];

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> coins(n);
    for (int &x: coins) cin >> x;
    sort(coins.begin(), coins.end());
    set<int> loc;
    loc.insert(0);
    ways[0]=1;
    ready[0]=true;
    while (!loc.empty()) {
        set<int> curr = loc;
        loc = set<int>();
        for (int x: curr) {
            for (int i: coins) {
                if (x+i>t) break;
                if (ready[x+i]) {
                    ways[x+i]+=ways[x];
                    ways[x+i]%=MOD;
                }
                else {
                    ways[x+i]=ways[x];
                    ways[x+i]%=MOD;
                    loc.insert(x+i);
                    ready[x+i]=true;
                }
            }
        }
    }
    cout << ways[t] << endl;
}