给你一个正整数$$$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$$$。
输入
第一行也是唯一一行包含整数 $$$n$$$ ($$$0 < n < 2^{200\,000}$$$) 的二进制表示形式,不带前导零。
例如,字符串 10 是数字 $$$2$$$ 的二进制表示,而字符串 1010 表示数字 $$$10$$$。
输出
打印一个整数 — 满足语句中描述的条件的三元组 $$$(a,b,c)$$$ 的数量以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
101
输出 #1
12
输入 #2
1110
输出 #2
780
输入 #3
11011111101010010
输出 #3
141427753
注意
在第一个测试用例中,$$$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$$$。