Ann 正在用最酷的灯光布置她的办公室。她使用非常长的 LED 灯带，其中每个独立的单元格每秒钟都会根据以下简单而优美的算法进行开关切换。在每一步中，每个单元格的状态（0 表示关，1 表示开）由其在灯带上的两个邻居（左侧和右侧）以及它自身的状态决定，具体规则如下表所示：
| 当前模式 | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| 中心单元格的新状态 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Ann 选择了一个初始的单元格配置，并对由此产生的动画感到惊叹。这与康威生命游戏（Conway’s Game of Life）非常相似，在稳定与混沌的边界上表现出有趣的特性。
输入格式
输入包含两行。
第一行包含初始配置，为一个由 16 个字符 0 和 1 组成的字符串。该字符串左侧和右侧的所有单元格均视为 0。
第二行包含要执行的步数 $N$。
输出格式
输出应包含一行，即最终配置中总的 1 单元格数量。
数据范围
- $0 \le N < 2^{60}$
- LED 灯带被认为足够长，以确保没有任何
1单元格会到达灯带的末端。
样例
输入格式 1
0001001101111100 5
输出格式 1
11
说明
输出为 11，因为我们有以下五个步骤：
...0000000010011011111000... ...0000000110111110001000... ...0000001111100010011000... ...0000011000100110111000... ...0000111001101111101000...
其中未显示的所有部分仅包含 0 单元格。