MOD = 998244353
TRANS = [6, 3, 7, 4, 1, 0]
s = input().strip()
dp = [0] * 7 + [1]
for c in map(int, s):
dp1 = [0] * 8
for i in range(8):
for k in TRANS:
if c:
dp1[k & i] += dp[i]
elif (k & i) == 0:
dp1[i] += dp[i]
dp = [x % MOD for x in dp1]
n = int(s, base=2) + 1
print((n**3 + 3 * n**2 - n - 3 * sum(dp)) % MOD)
Number of triangles | AND path in a binary tree |
Factorial equations | Removal of vertices |
Happy segments | Cyclic shifts |
Zoos | Build a graph |
Almost correct bracket sequence | Count of integers |
Differences of the permutations | Doctor's Secret |
Back to School | I am Easy |
Teddy and Tweety | Partitioning binary strings |
Special sets | Smallest chosen word |
Going to office | Color the boxes |
Missing numbers | Maximum sum |
13 Reasons Why | Friend's Relationship |
Health of a person | Divisibility |
A. Movement | Numbers in a matrix |
Sequences | Split houses |