def mod_exp(x,y,mod):
res = 1
while (y):
if (y % 2 == 0):
x = (x * x) % mod
y = y // 2
else:
y -= 1
res = (res * x) % mod
return res % mod
t = int(input())
for _ in range(t):
n = int(input())
s = input()
count = 1
last_element = s[0]
last_element_contig_len = 1
for i in range(1,n):
if (s[i]==last_element):
last_element_contig_len +=1
else:
last_element = s[i]
last_element_contig_len = 1
count += mod_exp(2, (last_element_contig_len - 1), 998244353)
print (count % 998244353)
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <stdlib.h>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define int unsigned long long int
#define f(i,a,n) for(int i = a; i < n; i++)
#define pii pair<int, int>
#define ff first
#define ss second
#define len(vec) (vec).size()
#define vi vector<int>
#define pb push_back
#define mp make_pair
int inf = LONG_LONG_MAX;
int mod = 998244353;
vi dp;
void tathastu()
{
int n;
cin>>n;
string s;
cin>>s;
int one=0,zero=0, ans=0,used=0;
string a;
f(i,0,n)
{
one+=s[i]=='1';
zero+=s[i]=='0';
int l=i+1;
if(s[i]=='1')
{
int req=(l-one);
used+=req;
int rem=(l-1)-used;
int val=(dp[rem])%mod;
ans=(ans+val)%mod;
one+=req;
}
else
{
int req=(l-zero);
used+=req;
int rem=(l-1)-used;
int val=(dp[rem])%mod;
ans=(ans+val)%mod;
zero+=req;
}
}
cout<<(ans%mod)<<"\n";
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int testcases;
cin>>testcases;
dp.resize(2*1e5+1);
dp[0]=1;
f(i,1,2*1e5+1)
dp[i]=(dp[i-1]*2)%mod;
while(testcases--)
tathastu();
return 0;
}169. Majority Element | 119. Pascal's Triangle II |
409. Longest Palindrome | 1574A - Regular Bracket Sequences |
1574B - Combinatorics Homework | 1567A - Domino Disaster |
1593A - Elections | 1607A - Linear Keyboard |
EQUALCOIN Equal Coins | XOREQN Xor Equation |
MAKEPAL Weird Palindrome Making | HILLSEQ Hill Sequence |
MAXBRIDGE Maximise the bridges | WLDRPL Wildcard Replacement |
1221. Split a String in Balanced Strings | 1002. Find Common Characters |
1602A - Two Subsequences | 1555A - PizzaForces |
1607B - Odd Grasshopper | 1084A - The Fair Nut and Elevator |
1440B - Sum of Medians | 1032A - Kitchen Utensils |
1501B - Napoleon Cake | 1584B - Coloring Rectangles |
1562B - Scenes From a Memory | 1521A - Nastia and Nearly Good Numbers |
208. Implement Trie | 1605B - Reverse Sort |
1607C - Minimum Extraction | 1604B - XOR Specia-LIS-t |