Trang trí lớp

Để chuẩn bị cho ngày lễ kỷ niệm của trường, các bạn trong lớp được giao nhiệm vụ trang trí hai bên tường lớp học bằng các dải màu. Mỗi bên tường sẽ được trang trí theo một quy luật riêng, lặp lại tuần hoàn vô hạn.

Cụ thể:

• Bên trái lớp học được trang trí theo một dãy màu \(a_1, a_2, \dots, a_n\), và dãy này sẽ lặp lại vô hạn: \(a_i = a_{i+n}\) với mọi \(i\).
• Bên phải lớp học được trang trí theo một dãy màu \(b_1, b_2, \dots, b_m\), và cũng lặp lại vô hạn: \(b_i = b_{i+m}\) với mọi \(i\).

Bạn Kino là người rất tinh mắt, muốn kiểm tra mức độ khác biệt giữa hai bên tường. Cụ thể, Kino chọn ra \(k\) vị trí đầu tiên (tính từ trái sang phải) và đo độ khác biệt màu sắc giữa hai bên tường ở mỗi vị trí. Độ khác biệt giữa hai màu \(a_i\) và \(b_i\) tại cùng vị trí được xác định bằng phép toán XOR bitwise: \(a_i \oplus b_i\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n, m \leq 10^5,\ 1 \leq k \leq 10^{18})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((0 \leq a_i \leq 10^{18})\).
• Dòng thứ ba chứa \(m\) số nguyên \(b_1, b_2, \dots, b_m\) \((0 \leq b_i \leq 10^{18})\).

Output

In ra một số nguyên duy nhất --- tổng độ khác biệt ở \(k\) vị trí đầu tiên, chia dư cho \(10^9 + 7\).

Example

10 5 30
5 16 2 10 7 2 4 20 5 12
4 11 14 23 5

435

3 2 10
1 6 4
5 2

33

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 18 & \(k \leq 2 \cdot 10^5\)

2 & 13 & \(n\) \(mod\) \(m = 0\)

3 & 30 & \(k \le 10^9\)

4 & 39 & Không có ràng buộc bổ sung

\hline
\endtabular