A15175 | XOR Triangle

You 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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

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$ .

The 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$ .

Print one integer — the number of triples $(a,b,c)$ satisfying the conditions described in the statement modulo $998\,244\,353$ .