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.