Special Numbers - Razorpay

Problem Preview

"A special number is a number in which: - Prime valued indices consist of prime digits - Non-prime valued indices consist of non-prime digits By indices in a number, we refer to the position of a digit from the left of the number. For example, 534 consists of 5 at index 1, 3 at index 2, and 4 at index 3. Note: - Prime valued indices are: 2, 3, 5, 7, etc. - Non-prime valued indices are: 1, 4, 6, 8, etc. You are given three numbers named as N, M, and K Your task is to find out how many N-digit special numbers can be formed that leave a remainder K when divided by M. Since the answer can be very large, print it by taking modulo with 1000000007. ### Problem ### Input ### Output ### Constraints - 1 ≤ T ≤ 20 - 1 ≤ N ≤ 500 - 1 ≤ M ≤ 500 - 0 ≤ K ≤ M - 1 ### Example If N = 3, M = 4, K = 2, then there exists only 5 such 3 digit special numbers. 122, 422, 622, 822, 922 All these numbers leaves a remainder 2 when divided by 4 and also follows prime valued indices have prime digits and non prime valued indices consist of non prime digits."