### 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

0)

 `{1,2,3}` `{3,4}` `"2"`
`Returns: 17`
 1^3 + 2^4 = 17.
1)

 `{2, 3, 4}` `{2, 3}` `"3"`
`Returns: 95`
 2^2 + 3^3 + 4^(2 + 1) = 95.
2)

 `{2, 3, 4}` `{2, 3}` `"5"`
`Returns: 192`
 2^2 + 3^3 + 4^(2 + 1) + 2^(3 + 1) + 3^(2 + 2) = 192.
3)

 `{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).

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8086

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11121&pm=8086

Relja

#### Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Math, Recursion