카드 마술

나는 여자친구 앨리스에게 보여 줄 카드 마술을 연습하고 있다. 확률에 기대는 마술이라 대부분 성공하지만 언제나 성공하지는 않는다.

먼저 카드 여러 장을 섞어 앞면이 보이도록 한 줄로 늘어놓는다. 테이블에는 카드가 적어도 열 장 있다. 앨리스는 앞에서 열 장 안에 있는 카드 한 장을 몰래 고른다. 즉 1 이상 10 이하의 비밀 숫자 $x_0$을 정한다. 그다음부터는 카드를 건너뛰며 고르기를 반복한다. 위치 $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) 중에서 균등한 확률로 정해진다고 가정한다.

내가 마지막으로 고른 카드 뒤에 남은 알 수 없는 카드의 수는 그 카드의 값보다 작다. 마지막 카드가 Q라면 그 뒤에 남은 알 수 없는 카드는 0장에서 9장 사이다.

입력은 여러 테스트 케이스로 이루어지며 파일이 끝날 때까지 이어진다. 각 테스트 케이스는 다음과 같다.

• 첫 줄에 정수 $n$과 $m$이 주어진다($1 \le n \le 100$, $1 \le m \le 10$). $n$은 내가 고른 카드의 수이고, $m$은 내가 처음 고른 카드의 위치다. 위치는 1부터 센다.
• 다음 줄에 내가 고른 카드 $n$장의 앞면이 고른 순서대로 주어진다. 마지막 카드까지 모두 포함한다. 각 앞면은 정수 $v$($2 \le v \le 10$)이거나 문자 J, Q, K, A 중 하나다.

각 테스트 케이스마다 앨리스가 나와 같은 카드에서 멈추는 시작 위치를 골랐을 확률을 한 줄에 출력한다.

이 확률은 유리수 $p/q$다. 위 제한에서 $q$는 $1\,000\,000\,007$의 배수가 되지 않으므로, $r \times q \equiv p \pmod{1\,000\,000\,007}$과 $0 \le r < 1\,000\,000\,007$을 만족하는 정수 $r$이 정확히 하나 있다. 그 $r$을 출력한다. 확률이 정확히 $1/10$이면 $700000005$를 출력한다.