Monk and Palindromes
Tag(s):

## Disjoint Set, Medium

Problem
Editorial
Analytics

Monk loves maths and is always curious to learn new things. Recently, he learned about palindromes. Now, he decided to give his students a problem which uses maths and the concept of palindromes. So, he wants the students to find how many different numbers they can create according to the following conditions. He will give the students an integer N which will denote the total number of digits in the final number. Also he will provide them with Q conditions where these conditions will be of form A B where the number formed by concatenating the digits from the $A^{th}$ position to $B^{th}$ position is a palindrome. You can learn more about palindromes here.
Note- Numbers with leading zeros are also to be considered.

Input:
First line consists of the integer N denoting the number of digits in final number.
Next line consists of the integer Q denoting the number of conditions.
Next Q lines will be of the form A B which denotes that the number formed by concatenating the digits from the $A^{th}$ position to $B^{th}$ position of the final number is a palindrome.

Output:
Print the number of different numbers the students can create by following the conditions. Since the answer can be very large, print it modulo $10^9 + 7$.

Constraints:
$1 \leq N \leq 10^3$
$0 \leq Q \leq 10^4$
$1 \leq A \leq B \leq N$

SAMPLE INPUT
5
2
2 4
3 5
SAMPLE OUTPUT
1000

Explanation

According to the sample test case, the final number consists of 5 digits.
In first condition, we can see that the number consisting of digits from the $2^{nd}$ position to the $4^{th}$ position must be palindrome. So, this means that the $2^{nd}$ digit and the $4^{th}$ must be same whereas we can assign any digit to the $3^{rd}$ position.
Now in second condition, we can see that the number consisting of digits from the $3^{rd}$ position to the $5^{th}$ position must be palindrome. So, this means that the $3^{rd}$ digit and the $5^{th}$ must be same whereas we can assign any digit to the $4^{th}$ position.

So, we have $10$ possibilities to assign the $2^{nd}$ and $4^{th}$ digit. Similarly we have $10$ possibilities to assign the $3^{rd}$ and $5^{th}$ digit. Finally, the $1^{st}$ digit will also have $10$ possibilities. So, the different types of N digit numbers we can get is $10 \times 10 \times 10 = 1000$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Code Monk (Disjoint Set Union (Union Find))

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Disjoint Data Structures
• Data Structures > Disjoint Data Structures
• Data Structures > Disjoint Data Structures
• Data Structures > Disjoint Data Structures