Special Digit Numbers

You are given three integers: d, e, and f. Your task is to count the number of special d-digit numbers that satisfy a specific condition.

A d-digit number is considered special based on the digits allowed at each position (1-indexed, from left to right):

  If a digit's position k is a prime number (2, 3, 5, 7, ...), the digit at that position must be one of {2, 3, 5, 7}.

  If a digit's position k is not a prime number (1, 4, 6, 8, ...), the digit at that position must be one of {0, 1, 4, 6, 8, 9}.

Additionally, a valid d-digit number cannot have a leading zero.

The condition to satisfy is that when the special d-digit number is taken modulo e, the remainder must be exactly f.

You need to return the total count of such numbers, with the final answer taken modulo 10^9 + 7.

Input Format:

The first and only line of input contains three space-separated integers: d, e, and f.

Output Format:

Print a single integer representing the total count of such special numbers, modulo 10^9 + 7.

Note:

This problem is best solved using Dynamic Programming. A state dp[i][j] can represent the number of ways to form an i-digit special number prefix that results in a remainder of j when taken modulo e. You will need an efficient way to check for primality, such as a Sieve of Eratosthenes, pre-computed for all positions up to d.