Diversity

Time limit2sMemory limit1024 MB

Summary

Given two periodic integer sequences with periods n and m, compute the sum of a_i XOR b_i over the first k indices, modulo 1e9+7.

Level: Medium7 of 10
Topics: Math, Number theory, Bit manipulation
Solved: No attempts yet

Problem

Two infinite periodic integer sequences $a_i$ and $b_i$ are given. Their periods have lengths $n$ and $m$ . That is, the natural numbers $n$ and $m$ are given, along with $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ , where $a_i = a_{i+n}$ and $b_i = b_{i+m}$ hold for every natural number $i$ .

A natural number $k$ is also given. The diversity of the two sequences is the sum of $a_i \oplus b_i$ for $i = 1, 2, \dots, k$ . Here $\oplus$ is the bitwise exclusive OR, which sets a bit to 1 wherever the binary digits of the two numbers differ. For example, $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$ .

Calculate the diversity of the given sequences.

Input

The first line contains $n$ , $m$ , and $k$ ( $1 \le n, m \le 2 \cdot 10^5$ , $1 \le k \le 10^{18}$ ).

The second line contains $n$ integers $a_1, \dots, a_n$ ( $0 \le a_i \le 10^{18}$ ).

The third line contains $m$ integers $b_1, \dots, b_m$ ( $0 \le b_i \le 10^{18}$ ).

Output

Print the diversity modulo $10^9 + 7$ on a single line.

Examples2

Example 1
Input
```
3 2 10
1 6 4
5 2
```
Expected output
```
33
```

Example 2

Input

10 5 30
5 16 2 10 7 2 4 20 5 12
4 11 14 23 5

Expected output