import scala.annotation.tailrec
import scala.collection.mutable

object PrimeFrog {
  def primesUpTo(n: Int): Set[Int] = {
    // sieve of eratosthenes
    val candidatePrimes = mutable.BitSet.empty ++ (2 to n)
    val limit = math.sqrt(n).toInt
    for (i <- 2 to limit) {
      if (candidatePrimes(i)) {
        for (multiple <- i * i to n by i) {
          candidatePrimes -= multiple
        }
      }
    }

    candidatePrimes.toSet
  }

  def main(args: Array[String]): Unit = {
    val numSquares = args(0).toInt
    val croaks = args(1).map(_ == 'P').toList
    val primeFrog = new PrimeFrog(numSquares)
    println(primeFrog.pSequence(croaks))
  }
}

/*
 * This exhaustively calculates the probability of the sequence starting at
 * each square and averages them. The probability of the croak sequence
 * starting at each square is calculated recursively: first calculate the
 * probability of the first croak, then multiply that by the average of the
 * probabilities of the remaining croaks on the two adjacent squares (except on
 * the two ends, then we just take the one adjacent square).
 *
 * Efficiency comes from memoizing results: there will be many checks for the
 * same sequence on the same square.  We store the probability for each
 * trailing subsequence on each square, for a total of N * M map entries, where
 * N is the number of squares and M is the length of the sequence. Since we
 * calculate each of those at most once, runtime is also O(N + M); this assumes
 * that map equality checks on the list of croaks are constant time rather than
 * O(M): using object identity will accomplish this, and is possible given the
 * use of a linked list structure.
 *
 * Ideally, this would be tail recursive or iterative, but I was lazy and at
 * least in the problem statement the sequence is only 15 croaks long, which
 * gives us plenty of stack space.
 *
 * Finally, the problem statement asks for a result in the form of a reduced
 * fraction. I didn't bother doing this, though it would not change the
 * solution dramatically.
 */
class PrimeFrog(numSquares: Int) {
  import PrimeFrog._
  val primeSquares = primesUpTo(numSquares)
  // true => P, false => N
  val pSequenceStartingAtSquareMap = mutable.Map[(List[Boolean], Int), Double]()

  def pSequence(seq: List[Boolean]): Double = {
    (1 to numSquares).map(pSequenceStartingAtSquare(seq, _)).sum / (numSquares + 1)
  }

  def pSequenceStartingAtSquare(seq: List[Boolean], square: Int): Double = {
    seq match {
      case Nil => 1.0
      case s: ::[Boolean] => {
        pSequenceStartingAtSquareMap.getOrElseUpdate(
          (seq, square),
          calcPSequenceStartingAtSquare(s, square)
        )
      }
    }
  }

  def calcPSequenceStartingAtSquare(seq: ::[Boolean], square: Int): Double = {
    val pCurrentCroak = if (seq.head == primeSquares(square)) {
      2.0/3
    } else {
      1.0/3
    }

    lazy val pNextSquare = pSequenceStartingAtSquare(seq.tail, square + 1)
    lazy val pPrevSquare = pSequenceStartingAtSquare(seq.tail, square - 1)

    val pRemainingCroaks = square match {
      case 0 => pNextSquare
      case s if square == numSquares => pPrevSquare
      case _ => (pNextSquare + pPrevSquare) / 2
    }

    pCurrentCroak * pRemainingCroaks
  }
}