Submission #31262839

---

Source Code Expand

MOD = 10007
n = int(input())
s = input()
dp = [[[[0] * 2 for i in range(2)] for j in range(2)] for k in range(n)]
# dp[i][j][k][l] = i 日目の J 君が j，O 君が k，I 君が l であるときの，i 日目までのスケジュールの組み方の場合の数
# ただし，j, k, l は 0 (不参加) または 1 (参加)
for k in range(2):
    for l in range(2):
        if s[0] == "O" and k == 0:
            continue # O 君が責任者にもかかわらず不参加のスケジュールは除外
        if s[0] == "I" and l == 0:
            continue # I 君が責任者にもかかわらず不参加のスケジュールは除外
        dp[0][1][k][l] = 1 # 初日は J 君が参加必須
for i in range(1, n):
    for j in range(2):
        for k in range(2):
            for l in range(2):
                if s[i] == "J" and j == 0:
                    continue # J 君が責任者にもかかわらず不参加のスケジュールは除外
                if s[i] == "O" and k == 0:
                    continue # O 君が責任者にもかかわらず不参加のスケジュールは除外
                if s[i] == "I" and l == 0:
                    continue # I 君が責任者にもかかわらず不参加のスケジュールは除外
                for a in range(2):
                    for b in range(2):
                        for c in range(2):
                            if j * a + k * b + l * c == 0:
                                continue # 前日と共通の参加者が 1 人もいないスケジュールは鍵を開けられないので除外
                            dp[i][j][k][l] += dp[i - 1][a][b][c]
                            dp[i][j][k][l] %= MOD
answer = 0
for j in range(2):
    for k in range(2):
        for l in range(2):
            answer += dp[n - 1][j][k][l]
answer %= MOD
print(answer)

Submission Info

Judge Result