Binary Sorting (Easy)

Interview

Time limit1sMemory limit1024 MB

Summary

Given a binary string of length N, find its 0-based position after all length-N binary strings are sorted by popcount, then by their reversed value.

Level: Easy3 of 10
Topics: Bit manipulation, Sorting
Solved: No attempts yet

Problem

Hanbyeol collects every binary string of length $N$ and sorts them in a special way before using them. The sorting rules are as follows.

Sort by the number of 1s in the binary string, in ascending order.
If two strings have the same number of 1s, sort them by the ascending order of the string after it is reversed.

For example, when $N$ is 3, the strings are sorted in this order.

One day, his friend Sunlin came to him with a binary string of length $N$ and asked for its position in the sorted list. Hanbyeol has been busy and has not sorted the strings yet. Help him!

Input

The first line contains the length $N$ of the binary strings.

The second line contains a binary string $S$ of length $N$ .

The binary string may start with 0.

Output

Print the position of the given binary string after sorting all binary strings of the same length, counting from 0.

Constraints

$1\le N\le 10$

Examples1

Example 1
Input
```
5
01101
```
Expected output
```
22
```