22665번 - Deadly Dice Game 스페셜 저지다국어

문제

T.I. Financial Group, a world-famous group of finance companies, has decided to hold an evil gambling game in which insolvent debtors compete for special treatment of exemption from their debts.

In this game, each debtor starts from one cell on the stage called the Deadly Ring. The Deadly Ring consists of N cells and each cell is colored black or red. Each cell is connected to exactly two other adjacent cells and all the cells form a ring. At the start of the game, each debtor chooses which cell to start. Then he rolls a die and moves on the ring in clockwise order by cells as many as the number of spots shown on the upside of the die. This step is called a round, and each debtor repeats a round T times. A debtor will be exempted from his debt if he is standing on a red cell after he finishes all the rounds. On the other hand, if he finishes the game at a black cell, he will be sent somewhere else and forced to devote his entire life to hard labor.

You have happened to take part in this game. As you are allowed to choose the starting cell, you want to start from a cell that maximizes the probability of finishing the game at a red cell. Fortunately you can bring a laptop PC to the game stage, so you have decided to write a program that calculates the maximum winning probability.

입력

The input consists of multiple datasets.

Each dataset consists of two lines. The first line contains two integers N (1 ≤ N ≤ 2000) and T (1 ≤ T ≤ 2000) in this order, delimited with a single space. The second line contains a string of N characters that consists of characters ‘R’ and ‘B’, which indicate red and black respectively. This string represents the colors of the cells in clockwise order.

The input is terminated by a line with two zeros. This is not part of any datasets and should not be processed.

출력

For each dataset, print the maximum probability of finishing the game at a red cell in one line. Your program may output an arbitrary number of digits after the decimal point, provided that the absolute error does not exceed 10^-8.

제한

힌트