Game strike out#658
A strip of paper is divided into cells. Two players take turns choosing and crossing out exactly empty, consecutive cells. The winner is the one who makes the last move. Both players play optimally. The current state of the game is given. Determine which player will win.
The first line contains the numbers and (1 \leq k \leq n \leq 40). The second line contains characters: a capital Latin O represents an empty cell, and a capital Latin X represents a crossed out cell.
Print a single integer:
1 if the player who moves first will win;
2 if the second player will win;
0 if no moves are possible.
Example 1
Example 2
Example 3