Binary Transformation Maximum Decimal

You are given a binary string s and an integer n. Your task is to perform exactly n transformations on s using the following ordered steps in each transformation:

• Swap: Swap any two distinct characters in the current binary string.
• Reverse: Reverse the entire binary string.
• Invert: Invert all the bits (change 0 to 1 and 1 to 0).

After performing these operations exactly n times, convert the resulting binary string to its decimal representation and output that number.

Note: Analysis shows that regardless of the swap and reverse operations, the final result depends solely on the parity of n. In particular, if n is even, the final result is the decimal conversion of the original string; if n is odd, the final result is the decimal conversion of the bitwise inversion of the original string.

Examples:

Input:
101
2
Output:
5
Input:
110
1
Output:
1

</p>

inputFormat

The input consists of two lines:

1. The first line contains a binary string s (a sequence of characters '0' and '1').
2. The second line contains an integer n indicating the number of transformation operations to perform.

outputFormat

Output a single integer — the decimal value of the binary string after performing n transformations.

## sample

101
2

5