Median Compression

Given a binary string \(S\) of length \(N\) consisting of 0s and 1s, you can perform some operations. In each operation, you select a contiguous substring of length 3 and replace it with its median digit, i.e. the digit that is the middle one when the three digits are sorted (equivalently, the majority digit in that triple). You may perform any number of operations (including zero), in any order. Determine the number of distinct strings that can be obtained by applying a sequence of such operations. Since the answer can be large, output it modulo \(998244353\).

inputFormat

The first line contains a positive integer \(N\) \( (1 \leq N \leq \text{small})\) indicating the length of the string. The second line contains a binary string \(S\) of length \(N\) consisting of characters '0' and '1'.

outputFormat

Output a single integer, the number of distinct strings obtainable from \(S\) using the operations described, modulo \(998244353\).

sample

3
010

2