题目背景

译自 COCI 2024/2025 #2 T3。$\texttt{2s,0.5G}$。满分为 $90$。

题目描述

给定无限长的，周期长度为 $n$ 的非负整数序列 $a$ 的前 $n$ 项 $a_1,a_2,\cdots,a_n$。

给定无限长的，周期长度为 $m$ 的非负整数序列 $b$ 的前 $m$ 项 $b_1,b_2,\cdots,b_m$。

给定正整数 $k$，求出 $\displaystyle \left(\sum_{1\le i\le k} a_i\oplus b_i\right)\bmod \left(10^9+7\right)$。

输入格式

第一行，三个正整数 $n,m,k$。

第二行，$n$ 个正整数 $a_1,\cdots,a_n$。

第三行，$m$ 个正整数 $b_1,\cdots,b_m$。

输出格式

输出一行一个整数表示答案。

3 2 10
1 6 4
5 2

33

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

435

提示

对于 $100\%$ 的数据，保证：

• $1\le n,m\le 2\times 10^5$；
• $1\le k\le 10^{18}$；
• $0\le a_i,b_i\le 10^{18}$。

• 特殊性质 A：$n=m$。
• 特殊性质 B：$n=1$。