C. XOR Triangletime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given a positive integer n. Since n may be very large, you are given its binary representation.You should compute the number of triples (a,b,c) with 0 \leq a,b,c \leq n such that a \oplus b, b \oplus c, and a \oplus c are the sides of a non-degenerate triangle. Here, \oplus denotes the bitwise XOR operation.You should output the answer modulo 998\,244\,353.Three positive values x, y, and z are the sides of a non-degenerate triangle if and only if x+y>z, x+z>y, and y+z>x.InputThe first and only line contains the binary representation of an integer n (0 < n < 2^{200\,000}) without leading zeros.For example, the string 10 is the binary representation of the number 2, while the string 1010 represents the number 10.OutputPrint one integer — the number of triples (a,b,c) satisfying the conditions described in the statement modulo 998\,244\,353.ExamplesInput
101Output
12
Input
1110Output
780
Input
11011111101010010Output
141427753
NoteIn the first test case, 101_2=5.  The triple (a, b, c) = (0, 3, 5) is valid because (a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5) are the sides of a non-degenerate triangle.  The triple (a, b, c) = (1, 2, 4) is valid because (a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5) are the sides of a non-degenerate triangle. The 6 permutations of each of these two triples are all the valid triples, thus the answer is 12.In the third test case, 11\,011\,111\,101\,010\,010_2=114\,514. The full answer (before taking the modulo) is 1\,466\,408\,118\,808\,164.
101
12 
['bitmasks', 'brute force', 'constructive algorithms', 'dp', 'greedy', 'math', '*2500']