思路

题目要求求所有子矩阵中元素之和。已知对于一个 $n \times n$ 的矩阵，元素 $c[i][j]$（下标从 1 开始）出现在所有连续子矩阵中的次数为
因此所有子矩阵的和为

注意 $c[i][j] = a[i] \oplus b[j]$ 对于二进制数可写为

题目内容

小红有两个长度都为n的数组$a,b$，仅包含$0、1$

现在小红生成一个二维矩阵$c$，满足$c_{i,j}=a_i \bigoplus b_j$

现在小红想让你帮助她计算出其所有子矩阵的数值之和,结果对$10^9+7$取模。

输入描述

第一行一个整数$n(1≤n≤2×10^5)$,表示数组长度。

第二行$n$个整数，第个整数为$a_i(0≤a_i≤1)$。

第二行$n$个整数,第$i$个整数为$b_i(0≤b_i≤1)$。

输出描述

一个整数,表示矩阵$c$的所有子矩阵之和,结果对$10^9+7$取模

样例1

输入

3
1 0 1
0 1 0

输出

52