Binary String Randomizer

 

Problem Code: BINSTRRAND

Chef JJ is a fan of random events and calculating probabilities.

He designed a machine called the binary string randomizer (BSRand). BSRand takes a binary string A$A$ (say, of length N$N$) as input and then generates a binary string B$B$ (of the same length N$N$) as output using the following algorithm:

For each i$i$ from 1$1$ to N$N$,

• Uniformly randomly choose an integer j$j$ between 1$1$ and N$N$.
• Uniformly randomly choose an integer k$k$ between 1$1$ and N$N$.
• Set Bi:=Aj⊕Ak$B_i:=A_j\oplus A_k$ (where ⊕$\oplus$ represents the bitwise XOR operation)

Given a binary string A$A$, Chef JJ passes it through BSRand T$T$ times (i.e, first he passes the binary string A$A$ through the BSRand, then he passes the resultant binary string through BSRand again, and so on. This is done T$T$ times in total). Calculate the probability that the final binary string obtained is B$B$.

You need to print the probability of getting binary string B$B$ modulo 998244353$998244353$. Formally, let M=998244353$M=998244353$. It can be shown that the answer can be expressed as an irreducible fraction pq$\frac{p}{q}$, where p$p$ and q$q$ are integers and q≢0(modM)$q\not\equiv 0(\mathrm{mod}M)$. Output p⋅q−1(modM)$p\cdot q^{-1}(\mathrm{mod}M)$. In other words, output the (unique) integer x$x$ which satisfies 0≤x<M$0\le x<M$ and x⋅q≡p(modM)$x\cdot q\equiv p(\mathrm{mod}M)$.

Input Format

• The first line of the input contains two integers N$N$ and T$T$ - the length of the binary strings A$A$ and B$B$ and the number of times chef JJ passes the binary string through BSRand, respectively.
• The second line contains the binary string A$A$.
• The third line contains the binary string B$B$.

Output Format

Output the probability of getting binary string B$B$ from binary string A$A$ after passing it through BSRand T$T$ times, modulo 998244353$998244353$.

Constraints

• 1≤N≤100$1\le N\le 100$
• 1≤T≤106$1\le T\le {10}^6$

Sample Input 1 

2 1
01
11

Sample Output 1 

748683265

Sample Input 2 

2 1
00
11

Sample Output 2 

0

Sample Input 3 

2 2
11
00

Sample Output 3 

1

Explanation

Test Case 1$1$: For i=1$i=1$, we notice that the BSRand can select the following combinations of (j,k)$(j,k)$: (1,1),(1,2),(2,1),(2,2)$(1,1),(1,2),(2,1),(2,2)$. Out of these 4$4$ combinations, we see that only 2$2$ of them give 1$1$ as result. Therefore, the probability that B1$B_1$ becomes 1$1$ is 12$\frac{1}{2}$.

For i=2$i=2$, similarly the the probability that B2$B_2$ becomes 1$1$ is 12$\frac{1}{2}$.

Therefore the probability that the final string is 11$\mathtt{\text{11}}$ is 12⋅12=14=748683265(mod998244353)$\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}=748683265(\mathrm{mod}998244353)$.

Test Case 2$2$: It can be proved that there is no way to get string 11$\mathtt{\text{11}}$ from 00$\mathtt{\text{00}}$.