xor

Да разгледаме редица от цели положителни числа A1, A2, ..., An.
За подредицата
Ai1, Ai2, ..., Aik (1<=i1<i2<...<ik<= N) дефинираме xor-сума, като числото, получено при пресмятането на израза Ai1 xor Ai2 xor ... xor Aik. Подредицата може да има нула елементи (k=0) и в този случай xor-сумата е 0.

Задача

Да се определи максималната стойност на  xor-сумата, която може да бъде получена от някоя подредица на редицата A, както и броя на подредиците, за които xor-сумата е максимална.

Вход

Файлът xor.in съдържа на първия ред цяло положително число N, представляващо броя на елементите в редицата A. Вторият ред съдържа N цели положителни числа A1 A2 … An, разделени с интервали.

Изход

Файлът xor.out трябва да съдържа два реда. Първият ред трябва да съдържа максималната стойност на  xor-сумата, която може да бъде получена от подредица на редицата A. Вторият ред трябва да съдържа цялото положително число Nrsol, представляващо броя на подредиците, за които се достига максимумът на xor-сумата. Тъй като това число може да бъде много голямо, да се изведе само остатъкът при делението на числото Nrsol на 666777.

Ограничения

0 < N <= 5000
0 <= Ai <= 1018

Редицата
A се разглежда като подредица на самата себе си.
Операцията
xor представлява побитово  „изключващо или”. „Изключващо или” означава:

xor

0

1

0

0

1

1

1

0

Примери

xor.in

xor.out

Обяснение

xor.in

xor.out

Обяснение

3
11 9 5

14
1

Максималната xor-сума е 14. Подредицата с максималната xor-сума е само една {11, 5}.

5
1 2 3 4 5

7
4

Максималната xor-сума е 7. Подредиците с максималната xor-сума са: {2,5},{3,4},{1,2,4},{1,3,5}

Ограничение за време: 0.2 секунди на тест

Студент Marin Radu
Iaşi IT University
За връзка: rss1987@gmail.com

(превод на български: Стоян Капралов)