Merkkijonot

# 2023 loppukilpailu C
import itertools
from collections import Counter
n = int(input())

merkit = [input() for _ in range(n)]
MODULO = (10**9 + 7)

whole_string = "".join(merkit)
total_a = whole_string.count("a")
total_b = len(whole_string) - total_a
merkkarit = [(k.count("a"), k.count("b")) for k in merkit]
half_a = total_a // 2
half_b = total_b // 2


def naive():
    total = 0
    for i in range(n):
        for jonot in itertools.combinations(merkkarit, i):
            if sum(j[0] for j in jonot) * 2 == total_a and sum(j[1] for j in jonot) * 2 == total_b:
                total += 1
    print(total % MODULO)


def combine(x: "Counter[tuple[int,int]]", y: "Counter[tuple[int,int]]"):
    global half_a, half_b
    out = x + y
    for kx, vx in x.items():
        for ky, vy in y.items():
            k0 = kx[0] + ky[0]
            k1 = kx[1] + ky[1]
            if k0 <= half_a and k1 <= half_b:
                out[(k0, k1)] += vx * vy
    return out


def halve(x, d=0):
    # print("halving", d, x)
    if len(x) <= 1:
        return Counter(x)
    return combine(halve(x[:len(x) // 2], d + 1), halve(x[len(x) // 2:], d + 1))


def combinations():
    m = halve(merkkarit)
    # print(m)
    print(m[half_a, half_b] % MODULO)

    pass


combinations()

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

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: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

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: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED