레이팅 미적용Two infinite periodic sequences of integers, \(a_{i}\) and \(b_{i}\), are given, defined by their periods of lengths \(n\)
and \(m\), respectively. This means that the natural numbers \(n\) and \(m\) are given, as well as the numbers
\(a_{1}\), \(a_{2}\), . . . , \(a_{n}\) and \(b_{1}\), \(b_{2}\), . . . , \(b_{m}\), for which \(a_{i} = a_{i+n}\) and \(b_{i} = b_{i+m}\) hold for every natural number \(i\).
Additionally, given a natural number \(k\), we define the "diversity" of these two sequences as the sum \(a_{i}\) ⊕\(b_{i}\)
for each \(i = 1\), 2, . . . , k. (Here, ⊕denotes the bitwise exclusive OR operation, which produces ones in
the positions where the binary digits of the two numbers differ. For example, 5 ⊕3 = (101){2} ⊕(011) =
(110)_{2} = 6.)
Your task is to calculate the diversity of the given sequences.
In the first line, there are \(n\), \(m\), and \(k\) (\(1 \le n\), \(m \le 2 \cdot 10^{5}\), \(1 \le k \le 10^{18}\)), which are the numbers from the
task description.
In the second line, there are \(n\) integers \(a_{1}\), . . . , \(a_{n}\) (\(0 \le a_{i} \le 10^{18}\), \(i = 1\), 2, . . . , n).
In the third line, there are \(m\) integers \(b_{1}\), . . . , \(b_{m}\) (\(0 \le b_{i} \le 10^{18}\), \(i = 1\), 2, . . . , m).
Because the answer can be very large, output the remainder of the answer when divided by \(10^{9} + 7\) in a
single line.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 25점 | \(k \le 2 \cdot 10^{5}\) |
2 | 13점 | \(n = m\) |
3 | 9점 | \(n = 1\) |
4 | 43점 | No additional constraints. |
3 2 10
1 6 4
5 23310 5 30
5 16 2 10 7 2 4 20 5 12
4 11 14 23 5435