提示: 欢迎访问OurACM平台。
Problem 1711 奇怪的数组

Accept: 37    Submit: 264
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给你一组连续的无穷序列P,其中第i个元素定义如下:

P[i] = (A[i % Asize] ^ (B[i % Bsize] + i / Bsize)) % 1000000007。

其中%表示取模,^表示幂次方,/表示整除,Asize和Bsize分别表示数组A和数组B的元素个数。

P可以通过以下的伪代码生成:

int i = 0; while( true ){ P[i] = (A[i % Asize] ^ (B[i % Bsize] + i / Bsize)) % 1000000007; i = i + 1; }

现在给定数组A,B和一个整数N,你的任务就是计算出序列P中前N个元素的和(即P[0] +…+P[N - 1]),最后输出答案模上1000000007。

Input

输入数据的第一行为一个整数T,表示有T组测试数据。

接下来有T个测试数据,每组测试数据格式为:

Asize A0 A1 … A[Asize – 1] Bsize B0 B1 … B[Bsize – 1] N

其中,1 <= Asize,Bsize<=50,1 <= A[i],B[i] <= 10^9,1 <= N <=10^18。

Output

每个测试数据输出一行,为序列P中前N个元素的和。

Sample Input

2 3 1 2 3 2 3 4 2 3 2 3 4 2 2 3 3

Sample Output

17 95

Source

福州大学第六届程序设计竞赛

Submit  Back  Status  Discuss