다양성

두 개의 무한 주기 정수열 $a_i$와 $b_i$가 주어진다. 두 수열의 주기 길이는 각각 $n$과 $m$이다. 즉, 자연수 $n$, $m$과 수 $a_1, a_2, \dots, a_n$, $b_1, b_2, \dots, b_m$이 주어지며, 모든 자연수 $i$에 대해 $a_i = a_{i+n}$, $b_i = b_{i+m}$이 성립한다.

자연수 $k$도 주어진다. 두 수열의 다양성은 $i = 1, 2, \dots, k$에 대해 $a_i \oplus b_i$를 모두 더한 값이다. 여기서 $\oplus$는 비트 단위 배타적 논리합(XOR)으로, 두 수의 이진수에서 자릿값이 서로 다른 자리에 1을 만든다. 예를 들어 $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$이다.

주어진 두 수열의 다양성을 구하라.

첫째 줄에 $n$, $m$, $k$가 주어진다 ($1 \le n, m \le 2 \cdot 10^5$, $1 \le k \le 10^{18}$).

둘째 줄에 $n$개의 정수 $a_1, \dots, a_n$이 주어진다 ($0 \le a_i \le 10^{18}$).

셋째 줄에 $m$개의 정수 $b_1, \dots, b_m$이 주어진다 ($0 \le b_i \le 10^{18}$).

답이 매우 클 수 있으므로, 다양성을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.