Različitost

Δίνονται δύο άπειρες περιοδικές ακολουθίες ακεραίων, ~a_i~ και ~b_i~, που ορίζονται από τις περιόδους τους, μήκους ~n~ και ~m~, αντίστοιχα. Αυτό σημαίνει ότι δίνονται οι φυσικοί αριθμοί ~n~ και ~m~, καθώς και οι αριθμοί ~a_1~, ~a_2~, ~...~, ~a_n~ και ~b_1~, ~b_2~, ~...~, ~b_m~, για τους οποίους ισχύει ότι ~a_i = a_{i + n}~ και ~b_i = b_{i + m}~ για κάθε φυσικό αριθμό ~i~.

Επιπλέον, δίνεται ένας φυσικός αριθμός ~k~, και ορίζουμε την "ποικιλομορφία" αυτών των δύο ακολουθιών ως το άθροισμα ~a_i~ ⊕ ~b_i~ για κάθε ~i = 1, 2, ..., k~. (Εδώ, το σύμβολο "⊕" δηλώνει τη δυαδική πράξη αποκλειστικό Ή, η οποία παράγει ~1~ στις θέσεις όπου τα δυαδικά ψηφία των δύο αριθμών διαφέρουν. Για παράδειγμα, ~5~ ⊕ ~3 = (101)_2~ ⊕ ~(011)_2 = (110)_2 = 6.~)

Ο στόχος σας είναι να υπολογίσετε την ποικιλομορφία των δεδομένων ακολουθιών.

Είσοδος

Στην πρώτη γραμμή, θα δίνονται οι αριθμοί ~n~, ~m~ και ~k\;(1 \le n,m \le 2 * 10^5,\;1 \le k \le 10^{18})~, οι αριθμοί από την περιγραφή του προβλήματος.

Στη δεύτερη γραμμή, θα δίνονται ~n~ ακέραιοι ~a_1~, ~...~, ~a_n~ ~(0 \le a_i \le 10^{18}~, ~i = 1, 2, ..., n~).

Στην τρίτη γραμμή, θα δίνονται ~m~ ακέραιοι ~b_1~, ~...~, ~b_m\;(0 \le b_i \le 10^{18},\; i = 1, 2, ..., m)~.

Έξοδος

Δεδομένου ότι η απάντηση μπορεί να είναι πολύ μεγάλη, εκτυπώστε το υπόλοιπο της απάντησης όταν διαιρεθεί με το ~10^9 + 7~ σε μία γραμμή.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~25~	~k \le 2 * 10^5~
~2~	~13~	~n = m~
~3~	~9~	~n = 1~
~4~	~43~	Κανένας επιπλέον περιορισμός

Παραδείγματα

1ο

input

3 2 10
1 6 4
5 2

output

33

2ο

input

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

output

435