Count those numbers !
Practice
1 (1 votes)
Algorithms
Dynamic programming
Modular arithmetic
Easy Medium
Problem
7% Success 1371 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

Vanya loves all numbers divisible by the number M. Now, given 2 numbers N and M, she gives you the following task : Given 2 numbers N and M, you need to count the number of numbers consisting of N digits that have value greater than 0 and are divisible by M. All numbers should be valid numbers, and should not contain any leading zeros.

In retrospect, Vanya realized that this task might be just too easy for you, and adds the following constraint : She gives you X pairs of numbers, each pair consists of 2 numbers from 1 to 9. Given these pairs , assume one of them to be consisting of numbers a and b, you need to eliminate out all numbers in which a and b appear adjacent to each other.They should not be adjacent in any order, i.e \(a,b\) (in that order) as well as \(b,a\) (in that order) are not valid. After this elmination process, you need to report the number of valid numbers.

As the answer could be rather large, print it Modulo \(10^9+7\).

Input Format :

The first line of the input consists of a single integer T, denoting the number of test cases. The description of each test case is spread out as follows :

The first line of each test case consists of 3 integers N, M and X. Each of the next X lines contains 2 integers a and b, denoting the numbers a and b should not appear adjacent to each other in any of the valid numbers. It is guaranteed that there shall be no 2 pairs, where \(a_{i} = a_{j} \) and \(b_{i} = b_{j} \).

Output Format :

For each test case, print the answer on a new line. As the answer can be rather large, print it Modulo \(10^9+7\).

Constraints :

\( 1 \le T \le 10 \)

\( 1 \le N \le 10^3 \)

\( 1 \le M \le 100 \)

\( 1 \le X \le 81 \)

\( 1 \le a_{i} , b_{i} \le 9 \)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
5 votes
Tags:
Easy-MediumEasy-med
Points:30
35 votes
Tags:
Dynamic Programming簡単-普通Algorithms3 DimensionaldpEasy-Medium
Editorial

No editorial available for this problem.