MOD = 10**9+7 def count_gold_placements(n, markings): dp = [[0, 0] for _ in range(n+1)] dp[0][1] = 1 for i in range(1, n+1): if markings[i-1] == '<': dp[i][0] = dp[i-1][1] dp[i][1] = dp[i-1][1] elif markings[i-1] == '=': dp[i][0] = dp[i-1][0] dp[i][1] = dp[i-1][1] elif markings[i-1] == '>': dp[i][0] = dp[i-1][0] dp[i][1] = dp[i-1][1] elif markings[i-1] == 'o': dp[i][0] = dp[i-1][0] dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD elif markings[i-1] == '.': dp[i][0] = dp[i-1][0] * 2 % MOD