Special Numbers

Problem Statement

Special Numbers Problem Description By the index of a digit in a number we mean its position counted from the left of the number, starting at 1. For example, 534 has the digit 5 at index 1, the digit 3 at index 2 and the digit 4 at index 3. A number is called a special number when: every digit at a prime-valued index is a prime digit , and every digit at a non-prime-valued index is a non-prime digit . Prime-valued indices are 2, 3, 5, 7, 11, ... . Non-prime-valued indices are 1, 4, 6, 8, 9, 10, ... (1 is not a prime, so index 1 is always a non-prime index). The two digit groups are: prime digits: 2, 3, 5, 7 non-prime digits: 0, 1, 4, 6, 8, 9 (inferred -- the source names the index groups but does not list the digit groups. A digit is prime exactly when the one-digit number it denotes is prime, so 0 and 1 are non-prime digits.) You are given three numbers N , M and K . Find how many N-digit special numbers leave a remainder K when divided by M . Since the answer can be very large, print