Problems
Pebble
Pebble
This summer, Antun and Branka stumbled upon a very interesting beach, which was completely covered with plastic ’pebbles’ brought by the sea from the containers that fell from the cargo ships. They decided to take back with them n of these pebbles, some red and some blue. Now that autumn has arrived, they are playing with the pebbles and reminiscing about the warm summer days.
Their game proceeds as follows: in the beginning, they place the $n$ pebbles in a row. Then, Antun and Branka make moves in turn, each time removing one of the pebbles from one of the ends of the row, until someone obtains $k$ red pebbles, losing the game. Antun moves first and is wondering whether he could win regardless of the moves Branka makes. Please help him and write a program which will answer his question.
\InputFile
The first line contains two integers $n$ and $k~(1 \le k < n \le 350)$. The second line contains a sequence of $n$ characters $C$ or $P$, where $C$ denotes a red pebble, and $P$ denotes a blue pebble. The character $C$ appears at least $2 \cdot k - 1$ times.
\OutputFile
If Antun can win regardless of Branka’s moves, you should print "\textbf{DA}", otherwise print "\textbf{NE}".
Input example #1
4 1 CCCP
Output example #1
DA
Input example #2
8 2 PCPPCCCC
Output example #2
DA
Input example #3
9 1 PPCPPCPPC
Output example #3
NE