Merkkijonot

#include <bits/stdc++.h>


using namespace std;
using ll = long long;


int main(){

    int n;
    cin >> n;
    vector<string> words(n+1);
    words[0] = "#";
    int sum =0;
    for(int i = 1; i <= n; ++i){
        cin>>words[i];
        sum += (int)words[i].size();
    }    

    if(sum%2){
        cout << "0\n";
        return 0;
    }

    vector<int> cnt(n+1);
    int tot_cnt = 0;
    for(int i = 1; i <= n; ++i){
        for(char c : words[i]){
            if(c=='a'){
                cnt[i]++;
                tot_cnt++;
            }
        }
    }

    if(tot_cnt%2){
        cout << "0\n";
        return 0;
    }

    ll ans = 0;

    for(int mask = 1; mask < (1<<(n+1)); ++mask){
        int siz = 0;
        int a = 0;

        for(int i = 1; i <= n; ++i){
            if(mask&(1<<i)){
                siz += (int)words[i].size();
                a += cnt[i];
            }
        }

        if(siz == sum/2 && a == tot_cnt/2){
            ans++;
        }
    }

    cout << ans/2 << "\n";





}

/*
DONT GIVE UP
DO SOMETHING INSTEAD OF NOTHING
CHECK ARRAY BOUNDS
SPECIAL CASES N=1
*/

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: WRONG ANSWER

Test 9

Group: 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: WRONG ANSWER

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED