# Input: list of available patterns (separated by commas)
#        then blank line, then list of desired designs (one per line)
# Output: how many ways can designs be made by concatenating copies of
#         one or more patterns?

from functools import cache

@cache
def ways_possible(design):
  ways = 0
  for pattern in patterns:
    if design == pattern:
      ways += 1
    if design[:len(pattern)] == pattern:
      ways += ways_possible(design[len(pattern):])
  return ways

patterns = []
designs = []

found_blank_line = False
file = open("19_input.txt", "r")
for line in file:
  line = line.replace("\n", "")
  if line == "":
    found_blank_line = True
    continue
  if not found_blank_line:
    for pattern in line.split(", "):
      patterns.append(pattern)
    continue
  designs.append(line)

total = 0
for design in designs:
  total += ways_possible(design)
print (total)