"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/258705
"""

# 풀이 과정
# 일정 규칙성을 지닌 것으로 판단되어 점화식>dp 생각 접근
# 점화식 찾기
# 위에 삼각형이 있나 없나 여부에 따른 점화식의 변화
# 직전한을 수가 아닌 모양으로 표현해서 규칙성 찾아보기!
def solution(n, tops):
    reuslt = 0
    dp = [0] * (n + 1)  # 0~n
    # case 분류
    # \\ 실행 여부로 구분!
    i = [0] * (n + 1)  # 실행
    j = [0] * (n + 1)  # 비실행

    i[0] = 0
    j[0] = 1
    # 두번 째 항
    if tops[0] == 1:
        i[1] = 1
        j[1] = 3
    else:
        i[1] = 1
        j[1] = 2

    for k in range(1, n):
        if tops[k] == 1:
            i[k + 1] = (i[k] + j[k]) % 10007
            j[k + 1] = (i[k] * 2 + j[k] * 3) % 10007
        else:
            i[k + 1] = (i[k] + j[k]) % 10007
            j[k + 1] = (i[k] + j[k] * 2) % 10007

    return (i[n] + j[n]) % 10007