# [Solution] XOR Triangle solution codeforces – You are given a positive integer šn. SinceĀ šnĀ may be very large, you are given its binary representation.

XOR Triangle solution codeforces – You are given a positive integer šn. SinceĀ šnĀ may be very large, you are given its binary representation.

## [Solution] XOR Triangle solution codeforces

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.

## [Solution] 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


## [Solution] 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.