Periodic XOR Sum

Given two infinite periodic sequences of non-negative integers:

• The first sequence a has period n with its first n terms given as \(a_1,a_2,\cdots,a_n\).
• The second sequence b has period m with its first m terms given as \(b_1,b_2,\cdots,b_m\).

Also given a positive integer k, compute the following value modulo \(10^9+7\):

\[ S = \left(\sum_{i=1}^{k} \bigl(a_i \oplus b_i\bigr)\right) \bmod (10^9+7), \]

where \(\oplus\) denotes the bitwise XOR operation. Note that the sequences are periodic, that is:

\[ a_{i} = a_{((i-1) \bmod n) + 1}, \quad b_{i} = b_{((i-1) \bmod m) + 1}. \]</p>

Your task is to compute \(S\) efficiently.

inputFormat

The first line contains three integers n, m and k, where n and m are the periods of sequences a and b respectively, and k is the number of terms to consider.

The second line contains n space-separated non-negative integers: \(a_1, a_2, \dots, a_n\).

The third line contains m space-separated non-negative integers: \(b_1, b_2, \dots, b_m\).

outputFormat

Print a single integer representing \(S = \left(\sum_{i=1}^{k} (a_i \oplus b_i)\right) \bmod (10^9+7)\).

sample

3 2 4
1 2 3
4 5

23