Numbers

Time limit2sMemory limit1024 MB

Summary

Count K-digit numbers using K distinct digits once that are a sum of two distinct primes and, after removing all factors of M, leave a semiprime.

Level: Medium7 of 10
Topics: Math, Number theory, Brute force, Backtracking
Solved: No attempts yet

Problem

Consider the numbers that can be formed by using each of $K$ distinct digits from 0 to 9 exactly once. Count how many of them satisfy both conditions below. The leading digit of a number cannot be 0, so 0143 is not allowed.

The number can be expressed as the sum of two distinct primes.
If you divide the number by $M$ repeatedly until it is no longer divisible by $M$ , the result is the product of two primes. The two primes may be equal.

For example, take $K = 1$ and $M = 11$ . Among one-digit numbers, 5, 7, 8, and 9 satisfy condition 1, while 4, 6, and 9 satisfy condition 2. The only number satisfying both conditions is 9, so the answer is 1.

Input

The first line gives $K$ and $M$ .

Output

Print the number of numbers that satisfy both conditions.

Constraints

$1 ≤ K ≤ 5$
$2 ≤ M ≤ 10^9$
$K$ and $M$ are integers.

Examples2

Example 1
Input
```
1 11
```
Expected output
```
1
```
Example 2
Input
```
1 3
```
Expected output
```
0
```