StrangeArray | Topcoder Archive

Problem Statement

You are given an infinite sequence P, where the i-th member is defined as follows:

  P[i] = (A[i % A.size] ^ (B[i % B.size] + i / B.size)) % 1000000007

where % denotes modulo, ^ denotes exponentiation, / denotes integer division, and X.size represents the number of elements in X.

Alternatively, the following pseudocode can be used to calculate the elements of P successively:

int i = 0;
loop forever
	P[i] = (A[i % A.size] ^ B[i % B.size]) % 1000000007;
	B[i % B.size] = B[i % B.size] + 1;
	i = i + 1;
end of loop

You are given int[]s A and B, and a String N containing an integer. Calculate the sum of the first N elements of the sequence (i.e., P[0] + P[1] + ... + P[N - 1]), and return that sum modulo 1000000007.

Definition

Class:: StrangeArray
Method:: calculateSum
Parameters:: int[], int[], String
Returns:: int
Method signature:: int calculateSum(int[] A, int[] B, String N)
(be sure your method is public)

Constraints

A and B will each contain between 1 and 50 elements, inclusive.
Each element of A and B will be between 1 and 10^9, inclusive.
N will represent an integer between 1 and 10^18, inclusive, with no leading zeros.

Examples

```
{1,2,3}
```
```
{3,4}
```
```
"2"
```
```
Returns: 17
```
1^3 + 2^4 = 17.
```
{2, 3, 4}
```
```
{2, 3}
```
```
"3"
```
```
Returns: 95
```
2^2 + 3^3 + 4^(2 + 1) = 95.
```
{2, 3, 4}
```
```
{2, 3}
```
```
"5"
```
```
Returns: 192
```
2^2 + 3^3 + 4^(2 + 1) + 2^(3 + 1) + 3^(2 + 2) = 192.
```
{1, 2, 3, 4}
```
```
{1}
```
```
"1000000000"
```
```
Returns: 607570807
```
1^1 + 2^2 + 3^3 + 4^4 + 1^5 + 2^6 + ... + 4^1000000000 = 607570807 (mod 1000000007).

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.