Description

An exploration robot discovered an extensive mining area on planet Samuel. In this mining area, there are towering mountains and flat plains. To facilitate survey, the entire mining area is divided into $2^K \times 2^K$ grid cells.

For example, as shown below, when $K=2$, the mining area is a $4 \times 4$ grid:

Black denotes mountains, and white denotes plains.

The exploration space station has scanned and recorded detailed information about this mining area. Because the area is extremely large, the scientists use a special encoding method to record it.

• If the entire mining area is plains, the code is 0.
• If the entire mining area is mountains, the code is 1.
• Otherwise, divide the mining area evenly into 4 parts, as shown below:

Encode each part in order to obtain $S_1,S_2,S_3,S_4$. The code $S$ of the mining area is $2S_1S_2S_3S_4$. For example, in the figure above, the code of the mining area is: 2021010210001.

Xiaolian hopes you can, based on the given code, count how many grid cells in this mining area are plains.

Input Format

The first line contains an integer $K$, indicating the size parameter $K$ of the mining area ($1 < K < 50$).

The second line contains a code string composed of 0, 1, 2, with length at most $200$, representing the code of the mining area.

Output Format

Output a single integer, representing how many grid cells in the mining area are plains.

2
2021010210001

9

Hint

Translated by ChatGPT 5