USACO 2019 January Contest, Gold Problem 1. Cow Poetry

Problems and Contests
#1

http://www.usaco.org/index.php?page=viewproblem2&cpid=897&lang=en

Hello,

I can’t figure out where my mistake is.
I only pass the first test …

Thanks

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e8 + 7;

inline long long fast_exp(long long n, int k) {
  long long res = 1;
  while (k > 0) {
    if (k % 2) {
      res *= n;
      res %= MOD;
    }
    n *= n;
    n %= MOD;
    k /= 2;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  freopen("poetry.in", "r", stdin);
  freopen("poetry.out", "w", stdout);
  int n, m, k;
  cin >> n >> m >> k;
  vector<pair<int, int>> vec(n);
  for (auto& i: vec) cin >> i.first >> i.second;
  sort(vec.begin(), vec.end());
  vector<long long> dp(k + 1);
  dp[0] = 1;
  for (int i = 1; i <= k; ++i) {
    for (int j = 0; j < n && i - vec[j].first >= 0; ++j) {
      dp[i] += dp[i - vec[j].first];
      dp[i] %= MOD;
    }
  }
  vector<long long> score(n + 1);
  for (const auto& i: vec) {
    score[i.second] +=  dp[k - i.first];
    score[i.second] %= MOD;
  }
  vector<int> val(26);
  while (m--) {
    char c;
    cin >> c;
    ++val[c - 'A'];
  }
  long long ans = 1;
  for (int i: val) {
    if (!i) continue;
    long long cnt = 0;
    for (int j: score) {
      if (!j) continue;
      cnt += fast_exp(j, i);
      cnt %= MOD;
    }
    ans *= cnt;
    ans %= MOD;
  }
  cout << ans;
}
#2

Could you first explain how your solution works?

#3

I found the error, my modulo is wrong, 1e8 + 7 instead of 1e9 + 7 ^^