import bisect
input = open("input", 'r')

splitters = None
start = None
for row, line in enumerate(input):
    if splitters == None:
        splitters = [[] for _ in range(len(line))]
    for col, char in enumerate(line):
        if char == "S":
            start = (row, col)
        elif char == "^":
            splitters[col].append(row)

def beam_to_splitter(splitters, beam):
    beam_row, beam_col = beam
    splitters_in_col = splitters[beam_col]
    next_splitter = bisect.bisect_right(splitters_in_col, beam_row)
    if next_splitter == len(splitters_in_col):
        return None
    return (splitters_in_col[next_splitter], beam_col)

def part1(splitters, start):
    used_splitters = set()
    unresolved_splitters = [beam_to_splitter(splitters,start)]
    while unresolved_splitters:
        splitter = unresolved_splitters.pop()
        used_splitters.add(splitter)

        splitter_row, splitter_col = splitter
        for offset in [-1, 1]:
            new_beam = (splitter_row, splitter_col+offset)
            next_splitter = beam_to_splitter(splitters, new_beam)
            if not next_splitter or next_splitter in used_splitters:
                continue
            unresolved_splitters.append(next_splitter)

    return len(used_splitters)

def part2(splitters, start):
    splitter_multiverses = {}
    def multiverse_count(splitters, splitter):
        if splitter == None:
            return 1
        if splitter not in splitter_multiverses:
            splitter_multiverses[splitter] = 0
            splitter_row, splitter_col = splitter
            for offset in [-1, 1]:
                new_beam = (splitter_row, splitter_col+offset)
                next_splitter = beam_to_splitter(splitters, new_beam)
                splitter_multiverses[splitter] += multiverse_count(splitters, next_splitter)
        return splitter_multiverses[splitter]

    return multiverse_count(splitters, start)

print(part1(splitters, start))
print(part2(splitters, start))