该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

快速求和（sum）

题目背景

请注意本题特殊的时间限制与空间限制。

题目描述

给定 $n$ 与长度为 $2^n$ 的数组 $\{f_0,f_1,\dots,f_{2^n-1}\}$ 和长度为 $2^n$ 的数组 $\{F_0,F_1,\dots,F_{2^n-1}\}$，请你求出 $(\sum_{i=0}^{2^n-1} \sum_{j=0}^{2^n-1} F_i \times F_j \times f_{i \& j} \times f_{i | j}) \bmod 998244353$ 的值。

对于 $x,y$ 定义 $x \& y$ 表示 $x,y$ 的按位与，$x | y$ 表示 $x,y$ 的按位或。

输入格式

第一行一个数 $n$。

接下来一行 $2^n$ 个数表示 $f_0,f_1,\dots,f_{2^n-1}$ 的值。

接下来一行 $2^n$ 个数表示 $F_0,F_1,\dots,F_{2^n-1}$ 的值。

输出格式

输出一行一个数表示答案。

输入输出样例 #1

输入 #1

2
1 1 4 5
1 9 1 9

输出 #1

3499

样例文件下载

样例文件下载

说明/提示

对于所有数据，保证任意 $0 \leq i < 2^n$ 满足 $0 \leq f_i,F_i < 998244353$。

时空限制

时间限制：3s，空间限制：32MB。