C. XOR-треугольники
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое положительно число $$$n$$$. Так как $$$n$$$ может быть большим, вам дано его представление в двоичной системе счисления.

Вычислите количество троек целых чисел $$$(a,b,c)$$$ таких, что $$$0 \leq a,b,c \leq n$$$, и значение $$$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$$$.

Примеры
Входные данные
101
Выходные данные
12
Входные данные
1110
Выходные данные
780
Входные данные
11011111101010010
Выходные данные
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$$$.