Фокус с картами
Я учусь фокусам, чтобы впечатлить свою девушку Алису. Мой последний фокус — вероятностный, то есть он срабатывает в большинстве случаев, но не всегда. Чтобы выполнить фокус, я сначала тасую колоду игральных карт и выкладываю их в один ряд лицом вверх на столе. Затем Алиса тайно выбирает одну из первых десяти карт (то есть она выбирает x_0, секретное число от 1 до 10 включительно) и пропускает карты следующим образом: выбрав карту на позиции x_i с числом c(x_i) на лицевой стороне, она выбирает карту на позиции x_{i+1} = x_i + c(x_i). Валет (J), Дама (Q) и Король (K) считаются как 10, Туз (A) считается как 11. Вы можете предположить, что на столе есть как минимум десять карт.
Алиса прекращает эту процедуру, как только на позиции x_i + c(x_i) нет карты. Затем я выполняю ту же процедуру с случайно выбранной начальной позиции, которая может отличаться от позиции, выбранной Алисой. Оказывается, что часто я оказываюсь на той же позиции. Алиса очень впечатлена этим фокусом.
Однако меня больше интересует лежащая в основе математика. Учитывая мою случайно выбранную начальную позицию и лицевые стороны каждой выбранной карты (включая мою последнюю), можете ли вы вычислить вероятность того, что Алиса выбрала начальную позицию, заканчивающуюся на той же последней карте? Вы можете предположить, что ее начальная позиция выбрана случайно с равномерной вероятностью (между 1 и 10 включительно). Я забыл отметить карты, которые я пропустил, поэтому эти карты неизвестны. Вы можете предположить, что лицевая сторона каждой из неизвестных карт независима от других лицевых сторон карт и случайна с равномерной вероятностью из возможных лицевых сторон карт (то есть 2-10, J, Q, K и A).
Рисунок 1 – Иллюстрация первого примера ввода: моя начальная позиция — 2, поэтому я начинаю выбирать эту карту. Затем я продолжаю пропускать карты в зависимости от лицевой стороны карты. Этот процесс повторяется до тех пор, пока не останется недостаточно карт для пропуска (в этом примере: Q). За последней картой Q следует от 0 до 9 неизвестных карт, так как Q считается как 10.
Входные данные
Для каждого теста:
Строка, содержащая два целых числа n (1 ≤ n ≤ 100) и m (1 ≤ m ≤ 10), где n — количество выбранных карт, а m — позиция моей первой выбранной карты, начиная с 1.
Строка с n токенами, которые указывают лицевые стороны n выбранных карт (в порядке, включая последнюю карту). Каждая лицевая сторона карты указана либо как целое число x (2 ≤ x ≤ 10), либо как один символ (J, Q, K или A, как указано выше).
Выходные данные
Для каждого теста выведите одну строку, содержащую вероятность того, что Алиса выберет начальную позицию, которая приведет к той же последней карте. Ваш вывод должен иметь абсолютную ошибку не более 10^{-7}.