수

시간 제한2초메모리 제한1024 MB

요약

서로 다른 K개의 숫자를 한 번씩 써서 만든 수 중에서, 두 서로 다른 소수의 합이고 M으로 나누어떨어지지 않을 때까지 나눈 결과가 두 소수의 곱인 수의 개수를 센다.

문제

0부터 9까지 $K$ 가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다.

예를 들어 $K$ 가 1이고 $M$ 이 11인 경우를 생각해보자. 한자리 수 중 1번 조건을 만족하는 수는 5, 7, 8, 9이고 2번 조건을 만족하는 수는 4, 6, 9이다. 두 조건을 모두 만족하는 수는 9이므로 이 경우에는 1개이다.

첫 번째 줄에 $K$ 와 $M$ 이 주어진다.

2가지 조건을 만족하는 수의 개수를 출력한다.