Company: Razorpay
Difficulty: medium
Special Numbers 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 . Input Format The first line contains an integer T (number of test cases). Each of the next T lines contains N , M , and K (three space-separated integers). Output Format Print the required answer for each test case in a new line. Constraints 1 ≤ T ≤ 20 1 ≤ N ≤ 500 1 ≤ M ≤ 500 0 ≤ K ≤ M - 1 Examples Input: 1 3 4 2 Output: 5 If N =