Rule 110

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:

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 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(0\le n<2^{60})$ of steps to perform.

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.

Examples

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.