A. Convolution XOR SUM
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$.

For a permutation $$$p_1, p_2, \ldots, p_n$$$ of $$$(1, 2, \ldots, n)$$$, let's define the score $$$S(p)$$$ of $$$p$$$ as follows.

  • $$${\displaystyle S(p) = \sum_{i = 1} ^{n} {a_{p_i}}\oplus b_i}$$$
where $$$\oplus$$$ denotes the bitwise XOR operation.

There are $$$n!$$$ permutations of $$$p$$$ of $$$(1, 2, \ldots, n)$$$. Find the sum, modulo $$$10^9+7$$$, of the scores of those permutations.

  • Formally, let $$$s_n$$$ be the set of the permutations of $$$(1, 2, \ldots, n)$$$. compute the following $$${\displaystyle \sum_{p \in s_n} {S(p)}} \bmod{10^9+7}$$$

A permutation is a sequence of $$$n$$$ integers from $$$1$$$ to $$$n$$$, in which all numbers occur exactly once. For example, $$$[1], [3,5,2,1,4], [1,3,2]$$$ are permutations, and $$$[2,3,2], [4,3,1], [0]$$$ are not.

Input

The first line of the input contains an integer $$$n$$$ $$$(1\le n \le 10^5)$$$ — the length of the array.

The second line of the input contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \le a_i \le 10^5)$$$ — the elements of the array $$$a$$$.

The third line of the input contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ $$$(1 \le b_i \le 10^5)$$$ — the elements of the array $$$b$$$.

Output

Print the sum of the scores, modulo $$$10^9+7$$$, for all permutations of length $$$n$$$.

Examples
Input
3
1 2 3
1 2 3
Output
24
Input
3
2 2 2
3 4 4
Output
78
Note

In the first case, all of the permutations of the array $$$a$$$ are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$ and the scores are $$$[0, 2, 6, 6, 6, 4]$$$. respectively. So, the result is $$$0+2+6+6+6+4=24$$$.