Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. XOR Triangle

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Input

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

Output

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

Examples

Input

101

Output

12

Input

1110

Output

780

Input

11011111101010010

Output

141427753

Note

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/28/2023 13:21:19 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|