C1467 [AHOI2005]矿藏编码

内存限制:256 MB 时间限制:1000 ms

题目描述

探险机器人在 Samuel 星球发现了一片广阔的矿藏区。在这个矿藏区中,有高耸的山峰,也有平坦的平地。为了方便考察,整个矿藏区被划分 $2^K \times 2^K$ 个格子区域。

例如下图,就是一个 $K=2$ 即 $ 4\times 4$ 的矿藏区:

image.png

其中黑色表示山峰,白色表示平地。

探险空间站已经将这片矿藏区的详细信息扫描并记录下来。由于矿藏区的面积实在太大,所以科学家们采用了一种特殊的编码方式记录。

(1) 如果这片矿藏区全部是平地,则编码为 $0$

(2) 如果这片矿藏区全部是山峰, 则编码为 $1$

(3) 否则,将矿藏区均匀划分成 $4$ 份,如下图所示:

image.png

输入格式

第一行有一个整数 $K$,表示有矿藏区的规模为($1 < K < 50$)。

第二行有一串编码,有 $0$、$1$ 组成,长度不超过 $200$,表示该矿藏区的编码。

输出

单行输出一个整数,表示矿藏区中一共有多少格子是平地。

样例

样例输入 1

2 2021010210001

样例输出 1

9

提示