#P18872. [HONI 2024/2025 #2] Različitost

[HONI 2024/2025 #2] Različitost

题目描述

有两个无限周期整数序列 a,ba,b,周期长度分别为 n,mn,m。输入给出 a1,…,ana_1,\ldots,a_n 和 b1,…,bmb_1,\ldots,b_m。对所有正整数 ii,都有 ai+n=aia_{i+n}=a_i 和 bi+m=bib_{i+m}=b_i。

求 ∑i=1k(ai⊕bi)\sum_{i=1}^k(a_i\oplus b_i) 对 109+710^9+7 取模的结果。⊕\oplus 表示按位异或。

输入格式

第一行三个整数 n,m,kn,m,k,满足 1≤n,m≤2⋅1051\le n,m\le2\cdot10^5、1≤k≤10181\le k\le10^{18}。

第二行 nn 个整数 aia_i,第三行 mm 个整数 bib_i。所有序列元素均在 [0,1018][0,10^{18}] 内。

输出格式

输出所求的和对 109+710^9+7 取模的结果。

子任务

子任务 分值 额外限制
1 25 k≤2⋅105k\le2\cdot10^5
2 13 n=mn=m
3 9 n=1n=1
4 43 无

样例

样例 1

输入

3 2 10
1 6 4
5 2

输出

33

样例 2

输入

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

输出

435