Hai dãy số nguyên tuần hoàn vô hạn, \(a_i\) và \(b_i\), được cho, được xác định bởi chu kỳ của chúng có độ dài \(n\) và \(m\), tương ứng. Điều này có nghĩa là các số tự nhiên \(n\) và \(m\) được cho, cũng như các số \(a_1, a_2, . . . , a_n\) và \(b_1, b_2, . . . , b_m\), mà \(a_i = a_{i+n}\) và \(b_i = b_{i+m}\) đúng với mọi số tự nhiên \(i\).

Ngoài ra, cho một số tự nhiên \(k\), chúng ta định nghĩa "sự khác biệt" của hai dãy này là tổng \(a_i ⊕ b_i\) cho mỗi \(i = 1, 2, . . . , k\). (Ở đây, ⊕ biểu thị phép toán XOR theo bit, tạo ra các bit \(1\) ở vị trí mà các chữ số nhị phân của hai số khác nhau. Ví dụ, \(5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6\))

Nhiệm vụ của bạn là tính toán sự khác biệt của các dãy đã cho.

Dữ liệu vào

• Trong dòng đầu tiên, có \(n, m\), và \(k\) \((1 \le n, m \le 2 \times 10^5, 1 \le k \le 10^{18})\), là các số từ mô tả bài toán.
• Trong dòng thứ hai, có \(n\) số nguyên \(a_1, . . . , a_n\) \((0 \le a_i \le 10^{18}, i = 1, 2, . . . , n)\).
• Trong dòng thứ ba, có \(m\) số nguyên \(b_1, . . . , b_m\) \((0 \le b_i \le 10^{18}, i = 1, 2, . . . , m)\).

Dữ liệu ra

• Vì câu trả lời có thể rất lớn, xuất phần dư của câu trả lời khi chia cho \(10^9 + 7\) trong một dòng duy nhất.

Chấm điểm

Input 1

3 2 10
1 6 4
5 2

Output 1

33

Input 2

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

Output 2

435