A binary string$^\dagger$ $b$ of odd length $m$ is good if $b_i$ is the median$^\ddagger$ of $b[1,i]^\S$ for all odd indices $i$ ($1 \leq i \leq m$).

For a binary string $a$ of length $k$, a binary string $b$ of length $2k-1$ is an extension of $a$ if $b_{2i-1}=a_i$ for all $i$ such that $1 \leq i \leq k$. For example, 1001011 and 1101001 are extensions of the string 1001. String $x=$1011011 is not an extension of string $y=$1001 because $x_3 \neq y_2$. Note that there are $2^{k-1}$ different extensions of $a$.

You are given a binary string $s$ of length $n$. Find the sum of the number of good extensions over all prefixes of $s$. In other words, find $\sum_{i=1}^{n} f(s[1,i])$, where $f(x)$ gives number of good extensions of string $x$. Since the answer can be quite large, you only need to find it modulo $998\,244\,353$.

$^\dagger$ A binary string is a string whose elements are either $\mathtt{0}$ or $\mathtt{1}$.

$^\ddagger$ For a binary string $a$ of length $2m-1$, the median of $a$ is the (unique) element that occurs at least $m$ times in $a$.

$^\S$ $a[l,r]$ denotes the string of length $r-l+1$ which is formed by the concatenation of $a_l,a_{l+1},\ldots,a_r$ in that order.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), where $n$ is the length of the binary string $s$.

The second line of each test case contains the binary string $s$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the answer modulo $998\,244\,353$.


-----Examples-----

Input
6
1
1
1
0
2
11
3
010
9
101101111
37
1011011111011010000011011111111011111
Output
1
1
3
3
21
365


-----Note-----

In the first and second test cases, $f(s[1,1])=1$.

In the third test case, the answer is $f(s[1,1])+f(s[1,2])=1+2=3$.

In the fourth test case, the answer is $f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$.

$f(\mathtt{11})=2$ because two good extensions are possible: 101 and 111.

$f(\mathtt{01})=1$ because only one good extension is possible: 011.

Difficulty: MEDIUM
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
import sys
import collections
import math
MOD = int(1000000000.0) + 7
MOD = 998244353
inf = 1e+20
input = sys.stdin.readline

def f():
	n = int(input())
	s = input()
	pre = 0
	c = 0
	res = 0
	for i in range(n):
		if pre != s[i]:
			c = 1
		else:
			c *= 2
		c %= MOD
		res += c
		pre = s[i]
	return res % MOD
for case in range(int(input())):
	print(f())


import math

def solve():
	n = int(input())
	ans = 1
	res = 1
	s = input()
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans = 1
		else:
			ans = 2 * ans % 998244353
			ans = ans % 998244353
		res = (ans + res) % 998244353
	print(res)
t = int(input())
for i in range(t):
	solve()


m = 998244353
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	ans = 0
	while i < n:
		c = 1
		j = i + 1
		while j < n and s[j] == s[i]:
			c += 1
			j += 1
		ans = (ans + (1 << c) - 1) % m
		i = j
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(ans, t) = (1, 1)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			t = t * 2 % 998244353
			ans = (ans + t) % 998244353
		else:
			t = 1
			ans = (ans + t) % 998244353
	print(ans)


for tt in range(int(input())):
	n = int(input())
	s = input()
	fx = [0] * n
	fx[0] = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			fx[i] = 1
		else:
			fx[i] = fx[i - 1] * 2 % 998244353
	print(sum(fx) % 998244353)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	t = input()
	d = 1
	dp = 1
	for i in range(1, n):
		if t[i] == t[i - 1]:
			dp = dp * 2 % mod
		else:
			dp = 1
		d = (d + dp) % mod
	print(d)


MOD = 998244353

def solve(n, s):
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(1, n):
		dp[i] = dp[i - 1] * 2 if s[i - 1] == s[i] else 1
		dp[i] %= MOD
	return sum(dp) % MOD
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = solve(n, s)
	print(ans)


t = int(input())
mod = 998244353
while t > 0:
	n = int(input())
	s = input()
	ret = 1
	pre = s[0]
	count = 1
	for i in s[1:]:
		if i == pre:
			count = count << 1
			count = count % mod
		else:
			pre = i
			count = 1
		ret += count
		ret = ret % mod
	print(ret % mod)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	if n == 1:
		print(1)
	else:
		count = 1
		curr = 1
		for i in range(1, n):
			if a[i] == a[i - 1]:
				curr = curr * 2 % 998244353
			else:
				curr = 1
			count = (count + curr) % 998244353
		print(count % 998244353)


t = int(input())
for _ in range(t):
	n = int(input())
	m = 998244353
	s = input()
	ans = 1
	prev = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			prev <<= 1
			ans += prev
		else:
			prev = 1
			ans += prev
		if ans > m:
			ans = ans % m
		if prev > m:
			prev = prev % m
	print(ans)


for i in range(int(input())):
	mod = 998244353
	n = int(input())
	s = input()
	ans = 1
	count = 0
	for i in range(1, n):
		count = count + ans
		count = count % mod
		if s[i] == s[i - 1]:
			ans = 2 * ans % mod
		else:
			ans = 1
	count = count + ans
	print(count % mod)


t = int(input())
mod = 998244353
for i in range(t):
	n = int(input())
	s = input()
	first = s[0]
	total = 1
	ans = 1
	for i in range(1, n):
		current = s[i]
		if current == first:
			ans = ans * 2
			ans %= mod
		else:
			ans = 1
			first = current
		total += ans
		total %= mod
	print(total)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	tot = 1
	cnt = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cnt = cnt * 2 % 998244353
			tot += cnt
		else:
			cnt = 1
			tot += cnt
		tot = tot % 998244353
	print(tot)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 1
	curr = 1
	mod = 998244353
	for i in range(1, n):
		if s[i] == s[i - 1]:
			curr = (curr + curr) % mod
		else:
			curr = 1
		ans = (ans + curr) % mod
	print(ans)


t = int(input())
while t:
	n = int(input())
	s = input()
	mod = 998244353
	ans = 1
	pre = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			pre = pre * 2
			pre = pre % mod
			ans = (ans + pre) % mod
		else:
			pre = 1
			ans = (ans + pre) % mod
	print(ans)
	t -= 1


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
M = 998244353
for _ in range(N()):
	c = 1
	n = N()
	dp = [0 for i in range(n)]
	dp[0] += 1
	if 'codeforces' == 28226329:
		print('Tanmay')
	s = S()
	for i in range(1, n):
		if s[i - 1] == s[i]:
			dp[i] = dp[i - 1] * 2 % M
			c = (c + dp[i]) % M
			continue
		dp[i] = 1
		c = (c + dp[i]) % M
	print(c % M)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	zeros_min = 0
	ones_min = 0
	summa = 0
	k = 1
	L = '2'
	for i in range(n):
		if s[i] == L:
			k <<= 1
		else:
			k = 1
		L = s[i]
		k %= 998244353
		summa += k
		summa %= 998244353
	print(summa)


for t in range(int(input())):
	n = int(input())
	s = list(map(int, list(input())))
	ans = 1
	curr = 1
	mod = 998244353
	for i in range(1, n):
		if s[i] == s[i - 1]:
			curr *= 2
		else:
			curr = 1
		ans += curr
		ans %= mod
		curr %= mod
	print(ans)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	if n == 1:
		return 1
	count = [[0, 0] for i in range(n)]
	dp = [0] * n
	dp[0] = 1
	ans = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			dp[i] = 1
		else:
			dp[i] = 2 * dp[i - 1] % mod
		ans = (ans + dp[i]) % mod
	return ans
mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(c) for c in input()]
	res = solve(s, n)
	print(res)


n = int(input())
for j in range(0, n):
	v = int(input())
	a = input()
	ans = 1
	lz = -1
	lf = -1
	l = [0] * v
	if a[0] == '0':
		lz = 0
	else:
		lf = 0
	l[0] = 1
	for j in range(1, v):
		if a[j] == '0':
			if a[j - 1] == '1':
				l[j] = 1
			else:
				l[j] = l[j - 1] * 2
		elif a[j - 1] == '0':
			l[j] = 1
		else:
			l[j] = l[j - 1] * 2
		l[j] = l[j] % 998244353
		ans = ans + l[j]
		ans = ans % 998244353
	print(ans)


from sys import stdin, stdout
input = stdin.readline
M = 998244353
pow2 = [1]
for i in range(200005):
	pow2.append(pow2[-1] * 2 % M)
for _ in range(int(input())):
	n = int(input())
	ans = 0
	count1 = 0
	count0 = 0
	for b in map(int, input().strip()):
		if b:
			count0 = 0
			count1 += 1
			ans = (ans + pow2[count1 - 1]) % M
		else:
			count1 = 0
			count0 += 1
			ans = (ans + pow2[count0 - 1]) % M
	print(ans % M)


for aa in range(int(input())):
	n = int(input())
	s = input()
	x = []
	a = 1
	b = 1
	c = 1
	v = 1
	for i in range(n):
		if s[i] == '0':
			v = 1
			b = 1
			if c == 1:
				x.append(1)
				c += 1
				continue
			if c > 1:
				a = (a * 2 % 998244353 + 998244353) % 998244353
				x.append(a)
		if s[i] == '1':
			a = 1
			c = 1
			if v == 1:
				x.append(1)
				v += 1
				continue
			if v > 1:
				b = (b * 2 % 998244353 + 998244353) % 998244353
				x.append(b)
	print(sum(x) % 998244353)


import math as mt
MAXN = 10001

def sieve():
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	d = {}
	while x != 1:
		if spf[x] in d:
			d[spf[x]] += 1
		else:
			d[spf[x]] = 1
		x = x // spf[x]
	return d
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 1
	ans = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			c *= 2
			c %= 998244353
			ans += c
			ans %= 998244353
		else:
			c = 1
			ans += c
	print(ans % 998244353)


import sys
import math
MOD = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	l = [[1] * 2 for _ in range(n)]
	for i in range(1, n):
		if string[i] == string[i - 1]:
			l[i][0] = l[i - 1][0] * 2
			l[i][0] %= MOD
			l[i][1] = l[i - 1][1]
		else:
			l[i][0] = l[i - 1][1]
			l[i][1] = l[i - 1][1]
	ans2 = 0
	for i in range(n):
		ans2 += l[i][0]
		ans2 %= MOD
	print(ans2)


test = int(input())
for tes in range(test):
	n = int(input())
	A = input()
	R = 998244353
	dp = [0] * n
	dq = [0] * n
	dp[0] = 1
	dq[0] = 1
	for i in range(1, n):
		if A[i] == A[i - 1]:
			dp[i] = dp[i - 1] * 2
			dp[i] %= R
			dq[i] = dq[i - 1]
		else:
			dp[i] = dq[i - 1]
			dq[i] = dq[i - 1]
	S = 0
	for i in range(n):
		S += dp[i]
		S %= R
	print(S)


import sys
import math
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().strip()
	s = '-' + s
	ones = 0
	zeros = 0
	ans = 0
	fixzeros = 0
	fixones = 0
	temp = 1
	prevpower = 0
	for m in range(1, n + 1):
		if s[m] == '1':
			ones += 1
			present = ones
			fixones = max(fixones, m - present)
		else:
			zeros += 1
			present = zeros
			fixzeros = max(fixzeros, m - present)
		fix = fixzeros + fixones
		newpower = m - 1 - fix
		diffpower = newpower - prevpower
		prevpower = newpower
		temp = int(temp * pow(2, diffpower, 998244353)) % 998244353
		ans = (ans + temp) % 998244353
	print(ans)


import sys
import math

def expmod(a, b, m):
	a = a % m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b = b >> 1
	return res

def power(x, y, p):
	res = 1
	while y > 0:
		if y & 1 != 0:
			res = res * x
		y = y >> 1
		x = x * x
	return res % p
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().strip()
	s = '#' + s
	ones = 0
	zeros = 0
	ans = 0
	fix0 = 0
	fix1 = 0
	temp = 1
	prevpower = 0
	for m in range(1, n + 1):
		if s[m] == '1':
			ones += 1
			present = ones
			fix1 = max(fix1, m - present)
		else:
			zeros += 1
			present = zeros
			fix0 = max(fix0, m - present)
		fix = fix0 + fix1
		newpower = m - 1 - fix
		diffpower = newpower - prevpower
		prevpower = newpower
		temp = int(temp * pow(2, diffpower, 998244353)) % 998244353
		ans = (ans + temp) % 998244353
	print(ans % 998244353)


mod = 998244353
T = int(input())
for t in range(T):
	l = int(input())
	a = input()
	cnt = 1
	ans = 1
	temp = []
	for i in range(1, l):
		if a[i] == a[i - 1]:
			temp.append(cnt)
			cnt += 1
		else:
			cnt = 1
			ans += 1
	Cnt = {}
	for t in temp:
		if t in Cnt:
			Cnt[t] += 1
		else:
			Cnt[t] = 1
	for (x, y) in Cnt.items():
		ans += y * pow(2, x, mod)
		ans = ans % mod
	print(ans)


import sys

def fn(a, l):
	if l == 1:
		return 1
	counter = 0
	total = 1
	for i in range(1, l):
		if a[i] == a[i - 1]:
			counter += 1
			total += pow(2, counter, 998244353)
		else:
			counter = 0
			total += 1
	return total
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	new_list = input[2 * i + 2].strip('\n')
	len_list = int(input[2 * i + 1].strip('\n'))
	out = fn(new_list, len_list) % 998244353
	print(out)


mod = 998244353
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = 1
	zer = 0
	one = 0
	c0 = 0
	c1 = 0
	if s[0] == '1':
		c1 += 1
	else:
		c0 += 1
	for i in range(1, n):
		if s[i] == '0':
			c0 += 1
			x = (c1 + i - c0) // 2 + 1
			if zer < x:
				zer = x
			ans += pow(2, i - one - zer, mod)
			ans = ans % mod
		else:
			c1 += 1
			x = (c0 + i - c1) // 2 + 1
			if one < x:
				one = x
			ans += pow(2, i - one - zer, mod)
			ans = ans % mod
	print(ans)