给定两个无限长的整数周期序列 $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$ 表示按位异或运算，它在两个数字二进制位不同的位置产生 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}, i = 1, 2, \dots, n$)。
第三行包含 $m$ 个整数 $b_1, \dots, b_m$ ($0 \le b_i \le 10^{18}, i = 1, 2, \dots, m$)。
输出格式
由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模后的余数。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 25 | $k \le 2 \cdot 10^5$ |
| 2 | 13 | $n = m$ |
| 3 | 9 | $n = 1$ |
| 4 | 43 | 无附加限制 |
样例
样例输入 1
3 2 10 1 6 4 5 2
样例输出 1
33
样例输入 2
10 5 30 5 16 2 10 7 2 4 20 5 12 4 11 14 23 5
样例输出 2
435