# pyright: strict import fnmatch from functools import cache from sys import stdin @cache def matching( pattern: str, groups: tuple[int, ...], length: int, min_offset: int = 0 ) -> int: if not groups: return 1 if "#" not in pattern else 0 total = 0 for offset in range(min_offset, length - sum(groups) - len(groups) + 2): base = "." * offset + "#" * groups[0] if not fnmatch.fnmatch(base, pattern[: len(base)]): continue total += matching( pattern[len(base) :], groups[1:], length - len(base), min_offset=1 ) return total inp: list[tuple[str, tuple[int, ...]]] = [] for line in stdin: pattern, rest = line.rstrip().split(maxsplit=1) groups = tuple(map(int, rest.split(","))) inp.append((pattern, groups)) print(sum(matching(pattern, groups, len(pattern)) for pattern, groups in inp)) print( sum( matching("?".join([pattern] * 5), groups * 5, len(pattern) * 5 + 4) for pattern, groups in inp ) )