A telecom crew is building a binary relay network shaped like a complete binary tree: a single master tower sits at the top (level 0), and every tower below has at most two child relays, a left one and a right one. The crew always finishes an entire level before starting the next, and within the deepest level (the one still being built) they always install relays strictly left to right — once a position in that level is skipped, no later position in that same level may be installed.

You are told that levels 0 through h-1 are already fully deployed (so h is the number of fully completed levels above the deepest one), and you are given the deepest level's installation record as a string of length 2^h: one character per possible position in that level, read left to right, where 1 means a relay is installed there and 0 means it is not.

Determine whether this record is consistent with left-to-right installation. If it is, report the total number of relays installed across the whole network (the fully deployed levels plus the deepest level). If it is not (some position is installed after an earlier position was skipped), report that the record is invalid.

Input format

Line 1: an integer h. Line 2: a string s of length exactly 2^h, consisting only of the characters 0 and 1.

Output format

If the record is consistent with left-to-right installation, print a single integer: the total number of relays installed, equal to (2^h - 1) plus the number of 1 characters in s. Otherwise, print exactly INVALID.

Constraints

• 0 <= h <= 20
• s has length exactly 2^h and contains only 0 and 1

2
1101

INVALID

3
11100000

10