Se considera sirul de numere naturale A₁, A₂, ..., A_n.
Numim suma xor a unui subsir A_i1, A_i2, ..., A_ik (1<=i₁<i₂<...<i_k<= N) valoarea obtinuta din evaluarea expresiei A_i1 xor A_i2 xor ... xor A_ik. Subsirul poate fi format si din 0 elemente (k=0). Pentru acest caz, suma xor este 0.

Cerinta

Determinati valoarea maxima a sumei xor ce se poate obtine pentru subsirurile sirului A precum si numarul de subsiruri pentru care suma xor este maxima.

Date de intrare

Fisierul xor.in contine pe prima linie numarul natural N reprezentând numarul de elemente din sirul A. Pe cea de-a doua linie se afla cele N valori A₁ A₂ … A_n, separate prin cate un spatiu.

Date de iesire

Fisierul xor.out va contine doua linii. Pe prima linie se va afla valoarea maxima posibila a sumei xor ce se poate obtine pentru subsirurile sirului A. Pe cea de-a doua linie se va afla numarul natural Nrsol care reprezinta numarul de subsiruri pentru care se obtine suma xor maxima. Fiindca acest numar poate fi foarte mare, se va afisa doar restul impartitii lui Nrsol la 666777.

Restrictii

0 < N <= 5000
0 <= A_i <= 10¹⁸
Sirul A este considerat un subsir al sau.
Operatia xor reprezinta disjunctia exclusiva, efectuata la nivel de biti. Prin disjunctie exclusiva se intelege:

Exemple

stud. Marin Radu
Facultatea de Informatica Iasi
Contact: rss1987@gmail.com