Cow Poetry

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 5e3 + 9;
const int MAXM = 1e5 + 9;
const int MAXS = 5e3 + 9;

const ll MOD = 1000000007;

ll bp (ll a, ll b) {
    if (b == 0)
        return 1;
    ll tmp = bp (a, b / 2);
    if (b & 1)
        return (((tmp * tmp) % MOD) * a) % MOD;
    return (tmp * tmp) % MOD;
}

ll dp[MAXS], r[MAXN];
unordered_map <char, int> umap;
pair <int, int> words[MAXN];

int main(){
    freopen ("poetry.in", "r", stdin);
    freopen ("poetry.out", "w", stdout);
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < n; i++)
        cin >> words[i].first >> words[i].second;
    for (int i = 0; i < m; i++) {
        char c;
        cin >> c;
        umap[c]++;
    }
    dp[0] = 1;
    for (int i = 0; i <= s; i++) {
        for (int j = 0; j < n; j++) {
            if (words[j].first + i > s)
                continue;
            if (words[j].first + i == s)
                r[words[j].second] = (r[words[j].second] + dp[i] + MOD) % MOD;
            else dp[words[j].first + i] = (dp[words[j].first + i] + dp[i] + MOD) % MOD;
        }
    }
    long long answer = 1;
    for (auto a: umap) {
        int freq = a.second;
        long long sum = 0;
        for (int k = 0; k <= n; k++) {
            if (r[k] == 0)
                continue;
            sum = (sum + bp (r[k], freq) + MOD) % MOD;
        }
        answer = (answer * sum + MOD) % MOD;
    }
    cout << answer % MOD << "\n";
    return 0;
}