々
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <unordered_map>
std::vector<std::pair<int, int>> pairs;
int mem[500*500*500];
// This is O(2^n) algo
int check(int i, std::pair<int, int> val)
{
if(val.first == 0 && val.second == 0)
return 1;
if(i == pairs.size())
return 0;
auto a = mem[i*500*500+val.first*500 +val.second];
if(a != -1)
return a;
std::pair<int, int> test;
test.first = val.first - pairs[i].first;
test.second = val.second - pairs[i].second;
int sum = 0;
if(test.second >= 0 && test.first >= 0)
sum += check(i + 1, test) % 1000000007;
sum += check(i + 1, val) % 1000000007;
mem[i*500*500+val.first*500 +val.second] = sum;
return sum % 1000000007;
}
int main()
{
int n;
std::cin >> n;
// Sub sum problem except sketchy???? so best case O(nm) ?????
// Only half has to be cheked
// pari (count of a, count of b) for 1 part
pairs.resize(n);
int totalA = 0;
int totalB = 0;
for(int i = 0; i < n; i++)
{
std::string str;
std::cin >> str;
// Count the intsances of a
for(auto c : str)
{
if(c == 'a')
{
totalA++;
pairs[i].first++;
}
else {
totalB++;
pairs[i].second++;
}
}
}
for(auto& a : mem)
a = -1;
//mem = { -1 };
if(totalA % 2 == 0 && totalB % 2 == 0)
std::cout << check(0, { totalA/2, totalB/2 }) << "\n";
else
std::cout << 0 << "\n";
}