Chef has a binary string S of length N. Chef wants to find two substrings of equal length, such that their [bitwise XOR] is maximised.

Formally, Chef wants to find L_{1}, R_{1}, L_{2}, and R_{2} such that:
1 ≤ L_{1} ≤ R_{1} ≤ N and 1 ≤ L_{2} ≤ R_{2} ≤ N
|R_{1} - L_{1} + 1| = |R_{2} - L_{2} + 1|, that is, the substrings have equal length;
S_{L_{1} \dots R_{1}} \oplus S_{L_{2} \dots R_{2}} is maximised, where \oplus is the bitwise XOR operation.

Output the maximum XOR value in decimal notation. Since the value can be large, output it module 10^{9}+7.

Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N denoting the length of string S.
- The second line of each test case contains a binary string S of length N containing 0s and 1s only.

------ Output Format ------ 

For each test case, output the maximum XOR value in decimal notation. Since the value can be large, output it module 10^{9}+7.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 2 \cdot 10^{6}$
$S$ contains $0$ and $1$ only.
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{6}$.

----- Sample Input 1 ------ 
3
4
1010
5
11111
3
011

----- Sample Output 1 ------ 
7
0
2

----- explanation 1 ------ 
Test case $1$: We can choose $L_{1} = 1, R_{1} = 3, L_{2} = 2,$ and $R_{2} = 4$. Thus, the chosen substrings are $101$ and $010$. The XOR of these substrings is $111$ whose decimal equivalent is $7$.

Test case $2$: We can choose $L_{1} = 2, R_{1} = 2, L_{2} = 4,$ and $R_{2} = 4$. Thus, the chosen substrings are $1$ and $1$. The XOR of these substrings is $0$ whose decimal equivalent is $0$.

Test case $3$: We can choose $L_{1} = 1, R_{1} = 2, L_{2} = 2,$ and $R_{2} = 3$. Thus, the chosen substrings are $01$ and $11$. The XOR of these substrings is $10$ whose decimal equivalent is $2$.

Difficulty: VERY_HARD
Tags: Greedy algorithms

Constructive algorithms

Ad-hoc
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	S = str(input())
	l = -1
	for i in range(N):
		if S[i] != S[0]:
			l = i
			break
	if l == -1:
		print(0)
		continue
	p = 0
	for i in range(l, N):
		if S[i] == S[l]:
			p += 1
		else:
			break
	p = min(p, l)
	ans = 0
	x = 1
	for i in range(N - 1, l - 1, -1):
		if S[i] != S[i - p]:
			ans = (ans + x) % 1000000007
		x = x * 2 % 1000000007
	print(ans)


def fun(s1, s2):
	md = 1000000007
	l = len(s1)
	ans = 0
	p = 1
	for i in range(l - 1, -1, -1):
		if s1[i] != s2[i]:
			ans = (ans + p) % 1000000007
		p = p * 2 % 1000000007
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	l = input()
	i = 0
	x = 0
	while i < n - 1:
		if l[i] != l[i + 1]:
			x = i + 1
			break
		i += 1
	c = 1
	i = x
	while i < n - 1:
		if c >= x:
			break
		if l[i] == l[i + 1]:
			i += 1
			c += 1
		else:
			break
	if x - c == -1:
		print(0)
		continue
	print(fun(l[x:], l[x - c:n - c]))


for _ in range(int(input())):
	n = int(input())
	mod = 10 ** 9 + 7
	s = input()
	idx = -1
	for i in range(0, len(s) - 1):
		if s[i] != s[i + 1]:
			idx = i + 1
			break
	count = 1
	if idx == -1:
		print(0)
		continue
	for i in range(idx, len(s) - 1):
		if s[i] != s[i + 1]:
			break
		else:
			count += 1
	if count > idx:
		ans = int(s[idx:n], base=2) ^ int(s[0:n - idx], base=2)
	else:
		ans = int(s[idx:n], base=2) ^ int(s[idx - count:n - count], base=2)
	print(ans % mod)


for _ in range(int(input())):
	n = int(input())
	s = input()
	flag = -1
	mod = 10 ** 9 + 7
	for i in range(1, n):
		if s[i] != s[0]:
			flag = i
			break
	else:
		print(0)
		continue
	xor_ = int(s[:n - flag], base=2) ^ int(s[flag:], base=2)
	(start, end) = (flag, n)
	for i in range(flag, n):
		if start == 0:
			break
		if s[i] == '0':
			start -= 1
			end -= 1
		else:
			break
	xor_ = max(xor_, int(s[start:end], base=2) ^ int(s[flag:], base=2))
	(start, end) = (flag, n)
	for i in range(flag, n):
		if start == 0:
			break
		if s[i] == '1':
			start -= 1
			end -= 1
		else:
			break
	xor_ = max(xor_, int(s[start:end], base=2) ^ int(s[flag:], base=2))
	print(xor_ % mod)


t = int(input(''))
m = 1000000007
l = [0] * 2000000
l[0] = 1
for i in range(1, 2000000):
	l[i] = l[i - 1] * 2 % m
for j in range(t):
	n = int(input(''))
	s = input('')
	if s.count('0') == n or s.count('1') == n:
		print(0)
		continue
	a = s.index('0')
	b = s.index('1')
	ans = 0
	z = 0
	if a < b:
		x = s[b:n]
		if '0' in x:
			z = x.index('0')
		if z == 0:
			y = s[a:n]
		elif b > z:
			y = s[b - z:n]
		else:
			y = s[a:n]
		for i in range(n - b):
			if x[i] != y[i]:
				ans = (ans % m + l[n - b - i - 1]) % m
	if a > b:
		(a, b) = (b, a)
		x = s[b:n]
		if '1' in x:
			z = x.index('1')
		if z == 0:
			y = s[a:n]
		elif b > z:
			y = s[b - z:n]
		else:
			y = s[a:n]
		for i in range(n - b):
			if x[i] != y[i]:
				ans = (ans % m + l[n - b - i - 1]) % m
	print(ans)


t = int(input())
for tr in range(t):
	n = int(input())
	s = input()
	n = len(s)
	i = 0
	switch_pos = 0
	while i < n - 1:
		if s[i] != s[i + 1]:
			switch_pos = i + 1
			break
		i += 1
	if not switch_pos:
		print(0)
		continue
	s2 = s[switch_pos:]
	max_num = 0
	i = switch_pos
	second_switch_pos = 0
	while i < n - 1:
		if s[i] != s[i + 1]:
			second_switch_pos = i + 1
			break
		i += 1
	if not second_switch_pos or second_switch_pos - switch_pos >= switch_pos:
		s1 = s[:len(s2)]
	else:
		s1 = s[switch_pos + n - second_switch_pos - len(s2):switch_pos + n - second_switch_pos]
	num = 0
	for i in range(len(s1)):
		if s1[i] != s2[i]:
			num = num + pow(2, len(s1) - 1 - i, 10 ** 9 + 7)
	print(num % (10 ** 9 + 7))


mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	(i0, i1) = (-1, -1)
	for i in range(n):
		if s[i] == '1':
			i1 = i
			break
	for i in range(n):
		if s[i] == '0':
			i0 = i
			break
	if i0 == -1 or i1 == -1:
		print(0)
		continue
	if i0 == 0:
		f0 = 10000 * n
		for i in range(i1 + 1, n):
			if s[i] == '0':
				f0 = i
				break
		ans = 0
		st = max(0, i1 - (f0 - i1))
		for i in range(i1, n):
			ans *= 2
			if s[i] != s[st]:
				ans += 1
			ans %= mod
			st += 1
		print(ans)
	else:
		f0 = 10000 * n
		for i in range(i0 + 1, n):
			if s[i] == '1':
				f0 = i
				break
		ans = 0
		st = max(0, i0 - (f0 - i0))
		for i in range(i0, n):
			ans *= 2
			if s[i] != s[st]:
				ans += 1
			ans %= mod
			st += 1
		print(ans)


import sys
from math import *
from bisect import *
mod_ = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 7)
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	flag = -1
	for i in range(1, n):
		if s[i] != s[0]:
			flag = i
			break
	else:
		print(0)
		continue
	xor_ = int(s[:n - flag], base=2) ^ int(s[flag:], base=2)
	(start, end) = (flag, n)
	for i in range(flag, n):
		if start == 0:
			break
		if s[i] == '0':
			start -= 1
			end -= 1
		else:
			break
	xor_ = max(xor_, int(s[start:end], base=2) ^ int(s[flag:], base=2))
	(start, end) = (flag, n)
	for i in range(flag, n):
		if start == 0:
			break
		if s[i] == '1':
			start -= 1
			end -= 1
		else:
			break
	xor_ = max(xor_, int(s[start:end], base=2) ^ int(s[flag:], base=2))
	print(xor_ % mod_)


def readlist():
	return list(map(int, input().split()))

def readint():
	return int(input())

def printbool(result: bool):
	print('YES') if result else print('NO')
modulo = 10 ** 9 + 7
T = readint()
for _ in range(T):
	N = readint()
	S = input()
	start = S[0]
	L = 0
	for i in range(len(S)):
		if S[i] != start:
			break
	for j in range(i + 1, N):
		if S[j] == start:
			break
	else:
		j = N
	j = max(0, 2 * i - j)
	best = int(S[i:], 2) ^ int(S[j:j + (N - i)], 2)
	print(best % modulo)


for _ in range(int(input())):
	N = int(input())
	S = str(input())
	isValid = '1' not in S or '0' not in S
	if isValid:
		print(0)
	else:
		find = str(S[0])
		i = 0
		for x in range(len(S)):
			if S[x] != find:
				i = int(x)
				break
		j = len(S)
		for x in range(i, len(S)):
			if S[x] != S[i]:
				j = int(x)
				break
		dis = min(i, j - i)
		print((int(S[i - dis:len(S) - dis], 2) ^ int(S[i:], 2)) % 1000000007)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
for t in range(int(input())):
	n = ni()
	s = si()
	if '1' not in s or '0' not in s:
		print(0)
		continue
	target = s[0]
	i = 0
	while i < len(s) and s[i] == target:
		i += 1
	j = int(i)
	while j < len(s) and s[i] == s[j]:
		j += 1
	d = min(i, j - i)
	l = len(s) - i
	print((int(s[i:], 2) ^ int(s[i - d:len(s) - d], 2)) % 1000000007)