razlicitost (COCI CONTEST_#2)
Time limit: 2 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: ad-hoc, number theory, prefix sum

# Task Različitost

Two infinite periodic sequences of integers, $a_i$ and $b_i$, are given, defined by their periods of lengths $n$ and $m$, respectively. This means that the natural numbers $n$ and $m$ are given, as well as the numbers $a_1, a_2, ..., a_n$ and $b_1, b_2, ..., b_m$, for which $a_i = a_{i+n}$ and $b_i = b_{i+m}$ hold for every natural number $i$.

Additionally, given a natural number $k$, we define the "diversity" of these two sequences as the sum $a_i \oplus b_i$ for each $i = 1, 2, ..., k$. (Here, $\oplus$ denotes the bitwise exclusive OR operation, which produces ones in the positions where the binary digits of the two numbers differ. For example, $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$.)

Your task is to calculate the diversity of the given sequences.

## Input

In the first line, there are $n$, $m$, and $k$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le k \le 10^{18}$), which are the numbers from the task description.

In the second line, there are $n$ integers $a_1, ..., a_n$ ($0 \le a_i \le 10^{18}$, $i = 1, 2, ..., n$).

In the third line, there are $m$ integers $b_1, ..., b_m$ ($0 \le b_i \le 10^{18}$, $i = 1, 2, ..., m$).

## Output

Because the answer can be very large, output the remainder of the answer when divided by $10^9 + 7$ in a single line.

## Scoring

| Subtask | Points | Constraints |
|---|---|---|
| 1 | 25 | $k \le 2 \cdot 10^5$ |
| 2 | 13 | $n = m$ |
| 3 | 9 | $n = 1$ |
| 4 | 43 | No additional constraints. |

## Examples

| Input | Input |
|---|---|
| 3 2 10 <br> 1 6 4 <br> 5 2 | 10 5 30 <br> 5 16 2 10 7 2 4 20 5 12 <br> 4 11 14 23 5 |
| Output | Output |
| 33 | 435 |

Starter code:

Grader code:

Setup script:

Evaluation script: