Dojave

Το μεγαλύτερο γεγονός της χρονιάς έκλεισε τραγικά για τις ομάδες της Κροατίας. Ο πιο επιδραστικός θεωρητικός του CERC όλων των εποχών, ο ιδρυτής της δημοφιλούς σελίδας CERC Tips, και στον ελεύθερο χρόνο του ένας εξαιρετικός μπασίστας, στην πιο πρόσφατη ερμηνεία του δεν κατάφερε να φτάσει την ομάδα του στους τελικούς.

Για να ξεπεράσει τα υπαρξιακά του προβλήματα, το υποκείμενο μας αφιερώνει χρόνο παίζοντας τυχερά παιχνίδια.​Ενδιαφέρεται ιδιαίτερα για το παρακάτω παιχνίδι:

Σας δίνεται ένας θετικός ακέραιος αριθμός ~M~. Ο πρωταγωνιστής μας βλέπει μπροστά του μια αναδιάταξη ενός πίνακα αριθμών ~0,\;1,\;2,\;\ldots,\;2^M-1~.
Ο υπολογιστής επιλέγει μια μη κενή συνεχόμενη υποακολουθία της δεδομένης αναδιάταξης, την οποία στη συνέχεια ανάβει πάνω από μια πρωτεύουσα μιας από τις χώρες της Νοτιοανατολικής Ευρώπης.

Ο έμπιστός μας, αφού καταπολεμήσει τα δάκρυα που προκλήθηκαν από αναμνήσεις παλιών εποχών, πρέπει να επιλέξει δύο ξεχωριστά στοιχεία της αναδιάταξης και να ανταλλάξει τις θέσεις του. Ο άνθρωπος μας κερδίζει εάν και μόνο αν το δυαδικό XOR των αριθμών στην αναμμένη υποακολουθία μετά την αντικατάσταση είναι ακριβώς ~2^M - 1~.

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

Βοηθήστε τον ήρωά μας να ξεπεράσει την κρίση ταυτότητάς του, ώστε η αγαπημένη μας σελίδα να μπορέσει να είναι ξανά πλήρως ενεργή.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~M\;(1 \le M \le 20)~,
Η ακόλουθη γραμμή περιέχει ~2^M~ αριθμούς διαχωρισμένους με κενό που συνθέτουν μια αναδιάταξη του πίνακα ~0,\;1,\;2,\;\ldots,\;2^M - 1~.

Έξοδος

Πρέπει να τυπώσετε τον συνολικό αριθμό των συνεχόμενων υποακολουθιών που ένας υπολογιστής μπορεί να ανάψει έτσι ώστε ο ήρωάς μας μπορεί να κερδίσει.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας το 50% των συνολικών πόντων, θα ισχύει ~1 \le M \le 14~.

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

input

2
0 1 2 3

output

9

Επεξήγηση του 1ου παραδείγματος:

Αν ο υπολογιστής επιλέξει την υποακολουθία ~[1\;2\;3]~, ο ήρωάς μας μπορεί να αντικαταστήσει τους αριθμούς 0 και 3. Σε αυτήν την περίπτωση, μπορεί πραγματικά να κερδίσει για κάθε επιλεγμένη συνεχόμενη υποακολουθία, εκτός από ολόκληρο τον πίνακα

input

3
3 7 0 4 6 1 5 2

output

33

Επεξήγηση του 2ου παραδείγματος:

Αν ο υπολογιστής επιλέξει ολόκληρο τον πίνακα ~[3\;7\;0\;4\;6\;1\;5\;2]~ ως φωτισμένη υποακολουθία, ο ήρωάς μας δεν μπορεί να αλλάξει το XOR της υποακολουθίας (που είναι 0), ανεξάρτητα από το ποια δύο στοιχεία εχουν ανταλλάξει θέση.

input

4
13 0 15 12 4 8 7 3
11 14 6 10 1 5 9 2

output

133