help

Statement

A binary string is a string consisting of $0$ s and $1$ s $.$ You are given a binary string s$=$s$\_(1)$s$\_(2)$dotss$\_($n$)$ of length n and an

integer k$>=0.$

For a binary string t$=$t$\_(1)$t$\_(2)$dotst$\_($m$)($m$>=2),$ transforming t means changing t to

t$\_(1)($t$\_(1)$o$+$t$\_(2))$t$\_(2)($t$\_(2)$o$+$t$\_(3))$t$\_(3)$dotst$\_($m$-1)($t$\_($m$-1)$o$+$t$\_($m$))$t$\_($m$)$

where o$+$ is the bitwise XOR operator. For example, $011$ transformed is $01101,$ and $10011$ transformed is

$110001101.$ Here is an image showing how $10011$ is transformed:

The beauty of a binary string t$=$t$\_(1)$t$\_(2)$dotst$\_($m$)($m$>=2)$ is the number of integers t$\_($i$)=$t$\_($i$+1)$tf$($t$)$f$(10010111)=3,$f$(010)=0$f$(000)=2$g$($t$)$f$($t$^(\text{'}))$t$^(\text{'})$tkg$($t$)$ss$[$l$,$r$]$s$\_($l$)$s$\_($l$+1)$cdotss$\_($r$)\backslash$sum Sample $1$ Explanation

There are three substrings of length at least $2$: $10,01,$ and $101.$ The substrings are transformed k$=2$ times

as follows:

$10->110->10110($beauty $1)$

$01->011->01101($beauty $1)$

$101->11011->101101101($beauty $2)$

The answer is $1+1+2=4.$ Sample Input $2$

$230$

$00$

Sample Output $2$

$75497471$

Sample $2$ Explanation

Remember to output the answer modulo $998244353.$