# XOR Triangle solution codeforces

## XOR Triangle solution codeforces

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𝑎,𝑏,𝑐𝑛0≤a,b,c≤n such that 𝑎𝑏a⊕b𝑏𝑐b⊕c, and 𝑎𝑐a⊕c are the sides of a non-degenerate triangle.

Here,  denotes the bitwise XOR operation.

You should output the answer modulo 998244353998244353.

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<𝑛<22000000<n<2200000) without leading zeros.

For example, the string 10 is the binary representation of the number 22, while the string 1010 represents the number 1010.

## XOR Triangle solution codeforces

Print one integer — the number of triples (𝑎,𝑏,𝑐)(a,b,c) satisfying the conditions described in the statement modulo 998244353998244353.

Examples
input

Copy
101

output

Copy
12

input

Copy
1110

output

Copy
780

input

Copy
11011111101010010

output

Copy
141427753


## XOR Triangle solution codeforces

In the first test case, 1012=51012=5.

• The triple (𝑎,𝑏,𝑐)=(0,3,5)(a,b,c)=(0,3,5) is valid because (𝑎𝑏,𝑏𝑐,𝑐𝑎)=(3,6,5)(a⊕b,b⊕c,c⊕a)=(3,6,5) are the sides of a non-degenerate triangle.
• The triple (𝑎,𝑏,𝑐)=(1,2,4)(a,b,c)=(1,2,4) is valid because (𝑎𝑏,𝑏𝑐,𝑐𝑎)=(3,6,5)(a⊕b,b⊕c,c⊕a)=(3,6,5) are the sides of a non-degenerate triangle.

The 66 permutations of each of these two triples are all the valid triples, thus the answer is 1212.

In the third test case, 110111111010100102=114514110111111010100102=114514. The full answer (before taking the modulo) is 14664081188081641466408118808164.