SOLVE
LATER
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\)
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\).
Challenge Name
Code Monk (Disjoint Set Union (Union Find))
Code Monk (Disjoint Set Union (Union Find))