Merkkijonot

#include <iostream>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
vector<string> v;
ll t[1000][2];
ll d[501][501][501][2];
ll M = 1000000007;
 
ll haku(ll k, ll a, ll b) {
  //cout << k << " " << a << " " << b << " " << t[k][0] << " " <<  t[k][1] << endl;
  ll s = 0;
  if (a == 0 && b == 0) return 1;
  if (a < 0) return 0;
  if (b < 0) return 0;
  if (k == -1) return 0;
  if (d[k][a][b][0]) return d[k][a][b][1];
  if (a >= t[k][0] && b >= t[k][1]) {
    s += haku(k-1, a-t[k][0], b - t[k][1]);
  }
  s += haku(k-1, a, b);
  d[k][a][b][1] = s%M;
  d[k][a][b][0] = 1;
  return s%M;
}
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  string s;
  ll a = 0;
  ll b = 0;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> s;
    v.push_back(s);
    for (auto u : s) {
      if (u == 'a') t[i][0] ++;
      else t[i][1] ++;
    }
    a += t[i][0];
    b += t[i][1];
  }
  if (a %2 != 0) cout << 0 << endl;
  else if (b%2 != 0) cout << 0 << endl;
  else {
    cout << haku(n-1, a/2, b/2)%M << endl;
  }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED