U509918 [COCI2024/2025 #2] Različitost

给出了两个无限的整数周期序列 $a_i$ 和 $bi$，长度为 $n$ 和 $m$ 的周期得到。换而言之，对于所有的 $i$，满足 $a_i=a_{i+n}$ 和 $b_i=b_{i+m}$。 现在，给出一个自然数 $k$，我们将这两个序列的**多样性**定义为 $a_i\oplus b_i$ 之和（其中 $1\le i\le k$，$\oplus$ 表示位运算异或。例如 $5\oplus 3=(101)_2\oplus (011)_2=(110)_2=6$）。 你需要去计算给定的数列的多样性。

第一行输入三个数 $n$、$m$ 和 $k$。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。 第三行 $m$ 个整数 $b_1,b_2,\dots,a_n$。

输出的结果可能非常大，所以请输出结果模 $10^9+7$ 的值。

对于 $100\%$ 的数据，$1\le n,m\le 2\times10^5,1\le k\le 10^{18}$，$0\le a_i,b_i\le 10^{18}$。 | Substask | 分数 | 约束条件 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | | $1$ | $25$ | $k\le2\times10^5$ | | $2$ | $13$ | $n=m$ | | $3$ | $9$ | $n-1$ | | $4$ | $43$ | 无 |