Migrated from Lutece 3238 Sentence know

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

不畏人间苦，不惧世上难，万般皆磨炼，有志终逞愿。

橘淳之介为了穿越回原来的【青蓝岛】，回到文乃的身边，正在与世界的法则展开着激烈的斗争。

他现在所处的世界可以用一个长度为 $n$ 的01串 $A$ 来描述，而他想要穿越到的世界同样可以用一个长度为 $n$ 的01串 $B$ 来描述。

淳之介每秒都会进行如下的操作：在 $[1,n]$ 中随机等概率选择一个正整数 $i$，并将 $A_i$ 翻转。

翻转操作的定义为：若 $A_i$ 在操作前为 $0$，则将其置为 $1$；同理若 $A_i$ 在操作前为 $1$，则将其置为 $0$。

现在淳之介想要知道，当他第一次将世界线改变为想要的世界时（即01串 $A=B$ ），操作次数的期望是多少。

Input

输入的第一行包括一个正整数 $n$，表示 01 串 $A,B$ 的长度。

接下来的两行每行一个长度为 $n$ 的 01 串，分别表示 $A,B$。

Output

输出一行一个整数，表示操作次数的期望对 $998244353$ 取模的结果。

Samples

2
00
01

3

4
1000
1110

665496254

5
01001
10111

665496277

Constraints

$1\le n\le 10^6$，输入的 $A,B$ 均为01串。

Note

样例1至样例3对应的操作次数的期望的分数表示形式分别为 $3,\frac{56}{3},\frac{125}{3}$。