Company: Razorpay_12oct
Difficulty: medium
Special Numbers Problem Description 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 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. Examples Example 1: Input: N = 3, M = 4, K = 2 Output: 5 Explanation: If N = 3, M = 4, K = 2, then there exist only 5 such 3-digit special numbers: 122, 422, 622, 822, 922. All these numbers leave a remainder 2 when divided by 4 and also follow the rules that prime valued indices have prime digits and non-prime valued indic