408289: GYM103081 B Rule 110

B. Rule 110time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ann is decorating her office with the coolest arrangement of lights ever. She is using very long LED strips, where each individual cell is switched on or off every second, according to the following simple and pretty algorithm. At each step, the status of each cell (0 for off and 1 for on) is determined from the status of its two neighbor cells on the strip (left and right) and its own status, according to the following table:

$$$$$$ \begin{array}{l|c|c|c|c|c|c|c|c} \textbf{Current pattern} & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000 \\ \hline \textbf{New state for center cell} & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ \end{array} $$$$$$

Ann is choosing an initial configuration for the cells and she marvels at the resulting animation, which happens to be highly similar to Conway's Game of Life, with interesting behavior on the boundary between stability and chaos.

Input

The input is composed of two lines.

• The first line contains the initial configuration, as a string of 16 characters 0 and 1. All the cells to the left and to the right of this string are considered to be 0.
• The second line contains the number $$$N$$$ of steps to perform.

Limits

• $$$0 \le N < 2^{60}$$$
• The LED strip is considered to be large enough to ensure that no 1-cells will ever reach the ends of the strip.

Output

The output should contain a single line with a single integer that is the total number of 1-cells in the final configuration.

ExampleInput

0001001101111100
5

Output

11

Note

Sample Explanation

the output is $$$11$$$ since we have the following five steps:

...0000000010011011111000...
...0000000110111110001000...
...0000001111100010011000...
...0000011000100110111000...
...0000111001101111101000...
...0001101011111000111000...

where everything not displayed contains only 0-cells.