RemoveGame

Fox Ciel and Toastman are playing the following game.


Initially, they are given a String. Each character of the String is either 'o' or 'x'. The first character of the String is always 'o' and the last character is always 'x'. 'o' characters are Ciel's characters, and 'x' characters are Toastman's characters.


The game is played as follows. Players take alternate turns, and Ciel makes the first turn. In each turn, the player must remove one of the opponent's characters. There must be at least one of the current player's characters to the left of the removed character, and one of the current player's characters to the right of the removed character.

For example, if the current state of the game is "oooxxoox" and it's Ciel's turn, she can remove either of the two 'x' characters in the middle, but she cannot remove the last 'x' character.


The game ends when a player cannot make a valid move. Once the game is over, each player counts the number of his/her characters that are still present in the String (i.e., characters that were not removed by the opponent during the game). The player with more characters wins. If both players have the same amount of characters, then it's a draw.

Both players use an optimal strategy. If a player can win, he/she will follow the strategy that guarantees that he/she wins and has the maximum number of characters at the end of the game. Otherwise, if a player can force the game to end in a draw, he/she will follow the strategy that does so. Otherwise, he/she will follow the strategy that minimizes the number of characters that the opponent has at the end of the game.


You are given a String field and an int R. The first character in field is 'o', the last character is 'x' and each of the other characters can be 'o', 'x' or '?'. You can obtain different initial placements of characters by replacing each '?' character in field with 'o' or 'x'.

Return the number of possible placements where Ciel wins and has at least R 'o' characters left at the end of the game.