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

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 \gt z$, $x+z \gt y$, and $y+z \gt x$.

给你一个正整数 $n$。由于 $n$ 可能非常大，你将获得其二进制表示。

你需要计算满足 $0 \leq a,b,c \leq n$ 的三元组 $(a,b,c)$ 的个数，使得 $a \oplus b$、$b \oplus c$ 和 $a \oplus c$ 构成一个非退化三角形的三条边。

此处，$\oplus$ 表示按位异或运算。

请将答案对 $998\,244\,353$ 取模后输出。

三个正数 $x$、$y$、$z$ 构成一个非退化三角形的充要条件是：
$x+y > z$，$x+z > y$，且 $y+z > x$。

The first and only line contains the binary representation of an integer $n$ ($0 \lt n \lt 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$.

第一行且仅有一行包含一个整数 $n$ 的二进制表示（$0 \lt n \lt 2^{200\,000}$），不含前导零。

例如，字符串 10 是数字 $2$ 的二进制表示，而字符串 1010 表示数字 $10$。

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

输出一个整数——满足题目描述中条件的三元组 $(a,b,c)$ 的个数，对 $998\,244\,353$ 取模。

In 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_2=5$。

• 三元组 $(a, b, c) = (0, 3, 5)$ 是合法的，因为 $(a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)$ 可构成一个非退化三角形的三条边。
• 三元组 $(a, b, c) = (1, 2, 4)$ 是合法的，因为 $(a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)$ 可构成一个非退化三角形的三条边。

上述两个三元组各自的 $6$ 种排列构成了全部合法三元组，因此答案为 $12$。

在第三个测试用例中，$11\,011\,111\,101\,010\,010_2=114\,514$。完整答案（取模前）为 $1\,466\,408\,118\,808\,164$。