cho.sh

Rabbit Movement

Given a colored board of at most 17 cells, simulate rabbits that move, collide, and shrink the board, then compute the expected number left from a uniformly random start.

Medium6SimulationCombinatoricsProbabilityImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

Rabbits gather to play a game.

The game is played on NN cells (N≥2N \ge 2) placed in a row. The cells are numbered from 0 to N−1N-1 from left to right, and each cell is painted white, black, or red.

rr rabbits start the game, each on a different cell. The set of starting cells is one of the ways to choose rr distinct cells, and every such way is equally likely.

The size of the board is the number of cells still on it, and it starts at NN. While the size of the board is greater than 2, the following steps repeat.

  1. Every rabbit moves to an adjacent cell at the same time. Write ss for the size of the board. The destination follows these rules.
    • A rabbit on cell 0 moves to cell 1.
    • A rabbit on cell s−1s-1 or cell s−2s-2 moves to the cell on its left.
    • Any other rabbit uses the color of the cell it stands on. On white it moves to the cell on its left, and on black it moves to the cell on its right. On red it moves to the cell on its left if it has never moved before, and otherwise it goes back to the cell it was on just before it arrived at the current cell.
  2. Once every rabbit has moved, each rabbit on a cell that holds two or more rabbits drops out of the game.
  3. The rightmost cell is removed from the board, so the size of the board decreases by 1. Under the rules above the rightmost cell is always empty once the moves are done.

When the game ends, the board holds 0, 1, or 2 rabbits. Compute the expected number of rabbits left on the board.

Input

The first line contains the colors of the board as a string. W is white, B is black, and R is red, and the length of the string is the number of cells NN. 2≤N≤172 \le N \le 17.

The second line contains the number of rabbits rr (1≤r≤N1 \le r \le N).

Output

Print the expected number of remaining rabbits as a reduced fraction on one line. The format is p/q, with q≥1q \ge 1 and the greatest common divisor of pp and qq equal to 1. If the expected value is an integer, write 1 as the denominator. For example, print 0/1 for an expected value of 0, and 2/1 for an expected value of 2.