Count Plain Cells in a Mining Area

On planet Samuel, an exploration robot discovered a vast mining area that has been divided into a grid of cells. The area consists of two types of terrain: plain (represented in white) and mountain (represented in black). The detailed information of the mining area was encoded using a special quadtree-based method.

The encoding process is as follows:

• If the entire region is plain, its encoding is 0.
• If the entire region is mountain, its encoding is 1.
• Otherwise, the region is divided uniformly into 4 quadrants in the order: top-left, top-right, bottom-left, bottom-right. Assume the encodings of these quadrants are \(S_1, S_2, S_3, S_4\) respectively. Then the encoding of the entire region is given by: $$2S_1S_2S_3S_4$$

For example, when \(K = 2\) the mining area is of size \(4 \times 4\) cells. One sample encoding is:

2021010210001

You are required to determine the number of plain cells in the mining area based on its encoding. Note that when the entire area is plain (i.e. encoded as 0), the number of plain cells is equal to \( \text{side}^2 \), where the side length is \(2^K\).

Input Format: The input consists of an integer \(K\) (where the side length of the area is \(2^K\)) on the first line, followed by a line containing the quadtree encoding string.

Output Format: Output the total number of plain (white) cells in the mining area.

inputFormat

The first line contains a positive integer \(K\) (\(1 \le K \le 10\)), representing that the mining area is of size \(2^K \times 2^K\). The second line contains a non-empty string representing the quadtree encoding of the mining area.

Note: The encoding follows these rules:

• 0: All cells in this region are plain.
• 1: All cells in this region are mountains.
• 2: The region is non-uniform and is subdivided into 4 quadrants (top-left, top-right, bottom-left, bottom-right); the encoding for the region is 2S1S2S3S4 with \(S_1, S_2, S_3, S_4\) being the codes for the four quadrants respectively.

outputFormat

Output a single integer that is the total number of plain cells in the mining area.

sample

2
2021010210001

9