write a go solution for E. Perfect Cuttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a string s consisting of characters 0, 1, and/or ?.Let's call a binary (consisting of 0 and/or 1) string perfect if you can cut the string into two non-empty parts: a prefix a and the suffix b, such that a_i>=b_i for each i from 1 to min(|a|,|b|).Your task is to calculate the number of ways to replace all the question marks (independently) with zeros and ones so that the resulting string is perfect mod. Two ways are considered different if there exists at least one position that has different characters in these two ways. Since the answer can be large, print it modulo 998244353.InputThe first line contains a single integer t (1<=t<=10^4) — the number of test cases.The only line of each test case contains a string s (2<=|s|<=2*10^5), consisting of characters 0, 1, and/or ?.Additional constraint on the input: the sum of the lengths of the strings s over all test cases doesn't exceed 2*10^5.OutputFor each test case, print a single integer — the number of ways to replace all the question marks (independently) with zeros and ones so that the resulting string is perfect, taken modulo 998244353.ExampleInput50?1011????110?00?1?Output1
0
15
2
3
NoteIn the first test case, the string 001 can be split into a prefix of length 1 and a suffix of length 2.In the fourth test case, the following strings can be obtained:  The string 11010, which can be split into a prefix of length 2 and a suffix of length 3;  The string 11000, which can be split into a prefix of length 4 and a suffix of length 1.. Output only the code with no comments, explanation, or additional text.