Strip of paper is divided into n cells. Two players make turns picking and crossing out exactly k empty adjacent cells. The winner is the one who made the last move. Both players follow the correct strategy. By the given position of the game find the winner.

Input

The first line contains numbers n and k (1 ≤ k ≤ n ≤ 40). Second line contains n symbols: the Latin capital 'O' - an empty cell, the Latin title 'X' - crossed out cell.

Output

Print a single number: 1 if the winner who first makes a move, and 2 - if you win the second; 0 - if the course can be done.