import sys from collections import defaultdict MOD = 998244353 def main(): N = int(sys.stdin.readline()) S = sys.stdin.readline().strip() answer = 0 dp_prev = defaultdict(int) # (mod, has_first) -> count for i in range(N): current_char = S[i] new_dp = defaultdict(int) # Case 1: new substring [i] if current_char == '?': new_dp[(0, False)] += 1 new_dp[(0, True)] += 3 new_dp[(1, True)] += 3 new_dp[(2, True)] += 3 else: d = int(current_char) if d == 0: new_dp[(0, False)] += 1 else: mod = d % 3 new_dp[(mod, True)] += 1 # Case 2: extend previous substrings for (prev_mod, prev_has_first), cnt in dp_prev.items(): if current_char == '?': if not prev_has_first: # Transition for ? where previous state has_first is False new_dp[(0, False)] += cnt new_dp[(0, True)] += 3 * cnt new_dp[(1, True)] += 3 * cnt new_dp[(2, True)] += 3 * cnt else: # Transition for ? where previous state has_first is True for m in [0, 1, 2]: d_count = 4 if m == 0 else 3 new_mod = (prev_mod + m) % 3 new_dp[(new_mod, True)] += cnt * d_count else: d = int(current_char) if not prev_has_first: if d == 0: new_dp[(0, False)] += cnt else: new_mod = d % 3 new_dp[(new_mod, True)] += cnt else: new_mod = (prev_mod + d) % 3 new_dp[(new_mod, True)] += cnt # Calculate contribution for current R current_contribution = 0 current_contribution += new_dp.get((0, False), 0) current_contribution += new_dp.get((0, True), 0) answer = (answer + current_contribution) % MOD # Update dp_prev for next iteration dp_prev = new_dp print(answer % MOD) if __name__ == '__main__': main()