Counting Valid n-Digit Numbers with Substring Equality Constraints

You are given a positive integer n representing the length of a large number, denoted as \(S_1S_2S_3 \cdots S_n\) where \(S_1\) is the most significant digit. In addition, you are given some constraints. Each constraint consists of four integers \(l_1, r_1, l_2, r_2\) which describe two substrings of equal length: \(S_{l_1}S_{l_1+1}\cdots S_{r_1}\) and \(S_{l_2}S_{l_2+1}\cdots S_{r_2}\). The constraint requires that these two substrings are exactly the same.

For example, when \(n=6\), a constraint with \(l_1=1, r_1=3, l_2=4, r_2=6\) requires that \(S_1S_2S_3 = S_4S_5S_6\). Thus numbers like 123123 and 351351 satisfy the condition, whereas 12012 (invalid because the length is not 6) and 131141 (invalid because the second digit and the fifth digit differ) do not.

Your task is to calculate the number of valid n-digit numbers that satisfy all the given constraints. Note that since \(S_1\) is the most significant digit, it cannot be zero, while other digits may be zero.

Hint: The constraints imply equality between certain positions in the number. You may use union-find (disjoint set) data structure to group positions which must have the same digit. For each group, if it contains the first digit, there are 9 possible choices (1 to 9), otherwise there are 10 choices (0 to 9). The answer is the product of possibilities for each group, modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n \leq 10^5,\, 0 \leq m \leq 10^5)\), representing the number of digits and the number of constraints respectively.

Each of the next \(m\) lines contains four integers \(l_1, r_1, l_2, r_2\) \(1 \le l_1 \le r_1 \le n,\, 1 \le l_2 \le r_2 \le n\) with \(r_1 - l_1 = r_2 - l_2\), describing a constraint that the substring \(S_{l_1}\) to \(S_{r_1}\) is equal to the substring \(S_{l_2}\) to \(S_{r_2}\).

outputFormat

Output a single integer, the number of valid n-digit numbers satisfying all the constraints, modulo \(10^9+7\).

sample

3 1
1 1 2 2

90