Problem description

Do bazy przybyła nowa dostawa N czołgów oraz N rodzajów amunicji. Każdą z amunicji możemy scharakteryzować liczbą a_i oznaczającą jej poziom kompatybilności, analogicznie c_i oznacza poziom kompatybilności czołgu i.

Generał wie, że jeżeli włoży amunicję typu i do czołgu typu j, to użyteczność tego czołgu wynosić będzie a_i XOR c_i.

Problem w tym, że podczas dostawy, nie została mu przekazana informacja, którą amunicję najlepiej włożyć do którego czołgu. Atak na Mickiewiczówek już jutro i generał nie ma czasu na zastanawianie się, jakie jest przydzielenie maksymalizujące sumaryczną użyteczność. Chce jednak wiedzieć, jaka jest sumaryczna użyteczność czołgów po każdym możliwym przydzieleniu amunicji, przy założeniu, że do każdego czołgu został przydzielony inny jej rodzaj modulo 10⁹ + 7

Wejście

W pierwszym wierszu wejścia znajduje się liczba N oznaczająca liczbę czołgów i rodzajów amunicji. W drugim wierszu wejścia znajduje się N liczb a₁, a₂, …, a_N określające poziom kompatybilności amunicji i. W trzecim wierszu wejścia znajduje się N liczb c₁, c₂, …, c_N określające poziom kompatybilności czołgu i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć sumaryczna użyteczność czołgów po wszystkich możliwych przydzieleniach modulo 10⁹ + 7.

Ograniczenia

1 ≤ N ≤ 100 000, 0 ≤ a_i, c_i ≤ 10⁹.

Przykład

2
0 1
1 4

10

4
4 2 3 7
1 0 5 6

360